精华内容
下载资源
问答
  • 一个集合的子集个数的计算方法

    万次阅读 2014-10-26 11:19:56
    假设一个集合包含n元素,要求计算

    假设一个集合包含n个元素,要求计算该集合的子集个数。

    该集合的所有子集,也叫该集合的幂集,比如集合{1,2,3}的所有子集为 空集,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}数一数,一共8个,由此推测为2的三次方,即2的三次幂。那么这个结论是否正确呢?

    方法1:

    一共集合有n个元素,它的子集的个数就是对这n个元素做组合,一共有n个位置可以组合,每个位置上该元素可以出现也可以不出现,所以最后总的个数为2的n次方。

    方法2:

    具有n个元素的集合的子集其实就是空集,含有一个元素的集合,含有两个元素的集合...含有n个元素集合,这集合的和就是,如图1所示。

    根据多项式的公式和定理知道,上面式子之和为2的n次方。


    展开全文
  • 求一个集合的子集个数的方法

    千次阅读 2019-03-18 16:44:47
    假设一个集合包含n个元素,要求计算集合的子集个数。 该集合的所有子集,也叫该集合的幂集,比如集合{1,2,3}所有子集为 空集,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}数一数,一共8个,由此推测为2三次方,即...

    假设一个集合包含n个元素,要求计算该集合的子集个数。

    该集合的所有子集,也叫该集合的幂集,比如集合{1,2,3}的所有子集为 空集,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}数一数,一共8个,由此推测为2的三次方,即2的三次幂。那么这个结论是否正确呢?

    方法1:

    一共集合有n个元素,它的子集的个数就是对这n个元素做组合,一共有n个位置可以组合,每个位置上该元素可以出现也可以不出现,所以最后总的个数为2的n次方。

    方法2:

    具有n个元素的集合的子集其实就是空集,含有一个元素的集合,含有两个元素的集合...含有n个元素集合,这集合的和就是,如图1所示。

    根据多项式的公式和定理知道,上面式子之和为2的n次方。

     

    展开全文
  • 简介 动机 Cardinality Filters SCF - Single Cardinality Filter ...参考资料简介介绍一数据结构“Cardinality Filter”来快速计算一组交集大小上限。且期望时间复杂度为O(|A|+|B|w\frac{|A| + |B|}{w}

    简介

    介绍一个新的数据结构“Cardinality Filter”来快速计算一组交集的大小上限。且期望的时间复杂度为O(|A|+|B|w),其中w表示字节大小。

    动机

    很多时候我们求交集并不在意交集的元素是什么,而是在意交集的个数是多少,比如在文本挖掘的top-k查询处理。
    top-k示例

    在上图中,有多个文档(如”DOOR”,”DRIVING”等),给定一个查询(可能是一个文档,也可能是一串单词集合),求与它交集最多的前K个文档。显然在这里我们并不关注每个文档与它的交集元素是什么,而是关注每个文档与它的交集个数是多少。因此可以应用本文介绍的“Cardinality Filter”方法来加速top-k查询问题。

    在该问题中,假设A为某个文档,B为查询文档,threshold为第K大的交集个数,则问题则变为求 |A ∩ B| > threshold,但实际上绝大多数|A ∩ B| ≪ threshold,在测试中有多达80% |A ∩ B| < 0.05 × threshold。
    因此我们可以利用求出|A ∩ B|的上限来加速这个问题,即|A ∩ B| ≦ Upper bound of |A ∩ B| ≦ threshold。这样子我们将跳过绝大数的|A ∩ B|的确切计算。

    Cardinality Filters

    CFs

    所谓的Cardinality Filters就是将原有的A,B集合在X的定义域中通过某种映射方法映射成Φ(A)和Φ(B),将 |A ∩ B| 问题转为 |Φ(A) ∩ Φ(B)|。
    Cardinality Filters有两种实现,Single Cardinality Filter(SCF)和 Recursive Cardinality Filter(RCF)。

    SCF - Single Cardinality Filter

    SCF定义Φ(A) = ( h(A), c(A) )
    其中h(A)表示hash后的值,而c(A)表示hash冲突里面非最小的值。注意这里h(A)是一个长度为⌈ |X| / N ⌉ 的bit序列,c(A)为int数组。下面用个例子来说明。
    SCF示例

    如图N=3,hash到[0,4]。
    A集合里有元素{7,8,10,12,14},通过hash分别映射到{2,0,2,4,4},显然发生了冲突,即2(7,10),4(12,14),故按照定义,这里h(A)={0,2,4},Φ(A)={10,14}。
    同样的在B集合里有元素{0,2,3,5,7,10,11,14},通过相同的hash分别映射到{1,2,4,0,2,2,1,4},这里的冲突为1(0,11),2(2,7,10),4(3,14),所以这里h(B)={0,1,2,4},Φ(A)={7,10,11,14}。
    故这里 |Φ(A) ∩ Φ(B)|= |h(A) ∩ h(B)| + |c(A) ∩ c(B)| = 3 + 2 = 5 。
    而 |A ∩ B| = 3 , 故 Φ(A) ∩ Φ(B) 符合 A ∩ B 的上限。

    直观上,之所以Φ(A) ∩ Φ(B)会是A ∩ B的上限,有如下两点:

    • 当不同的元素hash到同一值且未值上最小时(如图A中的8和B中的5都被hash到0),交集会额外多算;
    • 图中14被重复计算了2次,|h(A) ∩h(B)| 和 |c(A) ∩ c(B)| 都加了一次。

    下面给出SCF的严格定义:
    设X为全域(A, B ⊂ X),设H为hash值空间 H={ 0, 1,…,N, ⌈ |X| / N ⌉ - 1}。
    有 Φ: 2X>(2H,2X) : Φ(A) = (h(A), c(A)) (A ⊂ X)
    其中 h(A) = { h(x) | x ∈ A },值域为{0, ⌈ |X| / N ⌉ - 1 }.
    c(A) = { y∈A | (∃x∈A) (h(x) = h(y), x < y) }。
    得: |A∩B| ≦ |Φ(A)∩Φ(B)| := |h(A)∩h(B)| + |c(A)∩c(B)|

    其中 |h(A)∩h(B)|的计算可以通过Bit-wise AND操作(hash后为bit序列),而|c(A)∩c(B)|的计算可以通过简单的方法来计算,如linear merge algorithm或者hash或者二分。

    SCF的几点性质

    • 对于任意 A, B ⊆ X, |A ∩ B| ≤ |Φ(A) ∩Φ(B)|.

      证明:
      |A ∩ B| = |A ∩ B ∩ c(A) ∩ c(B)| + |(A ∩ B) \ (c(A) ∩ c(B))|,
      |Φ(A) ∩ Φ(B)| = |c(A) ∩ c(B)| + |h(A) ∩ h(B)|.
      所以要证 |A ∩ B| ≤ |Φ(A) ∩Φ(B)| 等价于证明:
      |A ∩ B ∩ c(A) ∩ c(B)| + |(A ∩ B) \ (c(A) ∩ c(B))| < |c(A) ∩ c(B)| + |h(A) ∩ h(B)|.
      显然有 |A ∩ B ∩ c(A) ∩ c(B)| ≤ |c(A) ∩ c(B)|,
      因此现在只需证明 |(A ∩ B) \ (c(A) ∩ c(B))| < |h(A) ∩ h(B)|.
      x ∈ (A ∩ B) \ (c(A) ∩ c(B))
      ⇒ x ∈ A ∧ x ∈ B
      ⇒ h(x) ∈ h(A) ∧ h(x) ∈ h(B)
      ⇒ h(x) ∈ h(A) ∩ h(B).
      且假设x < y 且 y c(A) ∩ c(B), 所以 y c(A) 或者 y c(B).
      若 y c(A),说明y是在hash(y)里最小的数,即不存在z ∈ A,使得 z < y and h(z) = h(y).
      若 y c(B),同理,则不存在z ∈ B, 使得 z < y and h(z) = h(y).
      因此,在 (A ∩ B) \ (c(A) ∩ c(B))里的任意两数x,y, 有 h(x) h(y).
      通过上述分析,对于 x ∈ (A ∩ B) \ (c(A) ∩ c(B)),都有唯一值h(x)与之对应,即说明了 |(A ∩ B) \ (c(A) ∩ c(B))| = |h((A ∩ B) \ (c(A) ∩ c(B)))|,
      而又有且 h(x) ∈ h(A) ∩ h(B), 所以h符合内射性(injectivity),固 h( (A ∩ B) \ (c(A) ∩ c(B)) )是 h(A) ∩ h(B)的子集。
      所以, | h( (A ∩ B) \ (c(A) ∩ c(B)) ) | |h(A) ∩ h(B)|
      所以, | (A ∩ B) \ (c(A) ∩ c(B)) | | h(A) ∩ h(B)|.
      而 |A ∩ B ∩ c(A) ∩ c(B)| ≤ |c(A) ∩ c(B)|, 得出结论:
      |(A ∩ B)| = |A ∩ B ∩ c(A) ∩ c(B)| + |(A ∩ B) \ (c(A) ∩ c(B))|
      |c(A) ∩ c(B)| + |h(A) ∩ h(B)| = |Φ(A) ∩Φ(B)|. 得证。

    • c(A)的期望size最多为 :N|A|22|X|

      证明:
      令 β 是对应于h(A)的比特数组,其长度为|H| = ⌈|X|/N⌉。
      hash函数将任意数x hash到任意bit位上的概率为 1|H|
      某一位bit上没有数的概率为:(11|H|)|A|
      因此 β 上bit上的有效位数为:|H|(1(11|H|)|A|)
      所以c(A)的期望size为:
      |A| − |h(A)|
      =|A||H|(1(11|H|)|A|)
      |A||H|(1(1|A||H|+|A|22|H|2))
      =|A|22|H|N|A|22|X|
      【有不等式:(1ϵ)n1nϵ+n2ϵ22

    • 应用SCF,对于集合A预期空间使用量最多为:|X|N+wN|A|22|X| bits.

      证明:
      |h(A)|+|c(A)|=|X|N+wN|A|22|X|

    • 应用SCF计算 |Φ(A)∩Φ(B)|的时间复杂度为:O(|X|Nw+N(|A|2+|B|2)|X|)。
      证明:
      对hash后的 βAβB 进行AND操作的时间复杂度为:O((|X|/N) · (1/w)),即O(|X|Nw)
      而用 linear merge algorithm计算 |c(A) ∩ c(B)| 时间复杂度为:
      O(|c(A)|+|c(B)|)=O(N(|A|2+|B|2)2|X|)=O(N(|A|2+|B|2)|X|)
      相加即得证。
    • The expected approximation ratio of SCF is at most 1+N|A||B||X||AB|.

    RCF - Recursive Cardinality Filter

    Recursive意为递归,故RCF顾名思义就是递归版本的SCF,递归的地方就是c(A),在SCF中我们可以得到 (h1(A), c1(A)),这里我们继续对得到的c1(A)应用SCF,则可以得到(h2(A), c2(A)),继续递归下去….
    定义递归层次为L,这样就可以得到 (h1(A), c1(A)), (h2(A),c2(A))… (hL(A),cL(A))
    所求集合上限则为: |Φ(A)Φ(B)|=Li=1|hi(A)hi(B)|+|cL(A)cL(B)|

    RCF

    下面给出RCF的严格定义:
    对于L层递归,有:
    Φ(A)=(H1(A),H2(A),...,HL(A),CL(A)),其中
    Hi(A)=hi(ci1(ci2(...c1(A)...))),
    Ci(A)=ci(ci1(...c1(A)...)), for i = 1, 2, … , L.

    Φ(A)Φ(B)=(H1(A)H1(B),H2(A)H2(B)...,HL(A)HL(B),CL(A)CL(B))
    |Φ(A)|=Li=1|Hi(A)|+|CL(A)|

    RCF的几点性质

    • 对于任意 A, B ⊆ X, |A ∩ B| ≤ |Φ(A) ∩Φ(B)|.
    • L=logmax|A|,|B|,r是一个比1大的常数,
      Ni=2i1|X|rmax|A|,|B|, (i=1, 2, … , L ),
      对于L层的RCF,计算| Φ(A) ∩ Φ(B) |的时间复杂度为O(|A|+|B|w)。
      【具体证明见论文。】

    参考资料

    论文《Faster Upper Bounding of Intersection Sizes》,文中部分结论证明见论文。

    展开全文
  • 在 Pharo Smalltalk 中计算集合统计数据的方法。 Collection 和 SortedCollection 类已经实现了均值 ( average )、标准差 ( stdev )、方差 ( variance ) 和中位 ( median )。 这包扩展了这些类来实现: 调和...
  • 方法实现传参并调用自定义method方法 import java.util.Scanner; public class MyCountCode { public static void main(String[] args) { Scanner sc1=new Scanner(System.in);//创建Scanner对象 String ...

    主方法实现传参并调用自定义的method方法

    import java.util.Scanner;
    
    public class MyCountCode {
    	public static void main(String[] args) {
    		Scanner sc1=new Scanner(System.in);//创建Scanner对象
    		String message=sc1.next();//next方法用来传递字符串
    		CountMethod.method(message);
    	
    		sc1.close();//关闭输入流,不写会抛出异常
    	}
    
    }
    

    新建一个CountMethod类,定义method方法用来实现字符计算

    import java.util.HashMap;//用到了HashMap集合
    
    public class CountMethod {
    	 public static void method(String mess) {
    		char[] mess1=mess.toCharArray();//toCharArray 方法 可以将字符串转换成字符数组
    		HashMap<Character,Integer> map =new HashMap<>();//创建HashMap对象,HashMap集合底层是哈希表结构
    		for(Character i:mess1) {//增强for 循环,i存储mess1集合里的键
    			if(map.containsKey(i)) {
    				Integer value = map.get(i);//get方法可根据键找到map集合里键对应的值
    				map.put(i, ++value);//键相同,用新的值覆盖原来的值
    				
    			}else {
    				map.put(i,1);//如果字符是第一次出现,则值为1
    			}
    		}
    		System.out.println(map)可直接打印map集合
    		System.out.println("-------------");
    		//遍历Map集合
    		for(Character j:map.keySet()) {//keySet方法将map返回key的set集合
    			Integer value=map.get(j);
    			System.out.println(j+" "+value);
    			
    		}
    	}
    }
    
    展开全文
  • 如何计算个集合的幂集

    千次阅读 2015-04-12 16:31:38
    这是看离散数学时候想到问题,如何用程序计算一个集合的幂集 ...一个含有n个元素的集合,其幂集包含2^n个集合,将这2^n个集合和2^n个数对应起来就行了。首先取0—2^n-1,把它们转化为二进制数,取其
  • (1) RDD全称为Resilient Distributed Dataset是一弹性、可复原分布式数据集,是Spark中最基本抽象,是一不可变、有多分区、可以并行计算的集合。 (2)RDD中并不装真正要计算的数据,而装是描述...
  • 其中重复数字,只保留一,把其余相同数字去掉,不同的数对应着 不同学生学号,然后再把这些 从小到大排序,按照排好顺序去找同学做调查,请你协助明明完成“>去重”与排序工作 import random ...
  • 如题,有什么比较快的方法可以计算给定1-9 9个数字排列个数呢 比较土算法: 1 定义一个1维数组,【1,2,3,4,5,6,7,8,9】 2 定义一个集合A,用来存储每个排列,一个排列就是一个有序的集合 2 遍历...
  • java 计算中位数方法

    千次阅读 2019-10-08 10:20:51
    最近工作需要 要求把python的代码写成java版本,python中有一个np.median()求中位数的方法,java决定手写一个 ...如果一个集合是偶数个,那么中位数就是按大小排列后,最中间那2个数的平均数。 比如: 1,2,3...
  • 字符 统计个数 所以我们可以使用HashMap<Character,Integer> 来存储。 第一步: 使用Scanner获取用户输入一个字符串。 第二步: 遍历字符串,获取每一个字符 String类的方法toCharA...
  • 计算方法

    2019-02-26 14:17:00
    Ck是样本集D中属于第k类样本子集,|Ck|表示该子集元素个数,|D|表示样本集合的元素个数 然后计算某个特征A对于数据集D经验条件熵H(D|A)为 Di表示D中特征A 取第i个值样本子集,Dik表示D...
  • N个数计算24点

    千次阅读 2010-09-21 00:08:00
    N个数计算24点 问题:  N个1到13之间自然数,找出所有能通过加减乘除计算(每个数有且只能用一次)得到24组合?   计算24点常用算法有:① 任取两个数计算后,将结果放回去,再...
  • 在这里我使用解体思路是这样,首先,建立一个集合,将数组一中数据放入集合,然后遍历数组二,当遇到与集合一中有相用数据时候,删除集合一中该数字,然后把该数字放入集合二,当遍历完数组二时候,集合...
  • 集合中选一个数与当前值进行位运算max 这是一个听来神仙东西。 先确定一下值域把,大概\(2^{16}\),再大点也可以,但是这里就只是写写,所以无所谓啦。 我们先看看如果暴力求怎么做,位运算需要给定\(01/10,00...
  • 相似度几种常见计算方法

    千次阅读 2020-07-15 15:30:58
    Jaccard(杰卡德)系数等于样本集交集的个数和样本集并集个数的比值。 Jaccard(杰卡德)距离是用两个集合中不同元素所占元素的比例来衡量两个集合(样本)的区分度。 Jaccard系数主要的应用的场景有: 1).过
  • 看了离散数学中的关系整理了一点关于n元集合中各种关系的计算,现写下这方便大家学习交流理解。其中有自反,对称,反自反,非对称等关系数的结论和计算方法,可供参考,
  • 字符 统计个数 HashMap<Character,Integer> 遍历字符串,获取每一个字符 1)String类的方法toCharArray,把字符串转换为一个字符数组,遍历数组。 2)String类的方法length()+charAt(索引) 使用Map集合中...
  • 为了建立用户精准兴趣模型以有效发现具有相似兴趣用户群,提出了一种针对微博短文本特征计算方法用于聚类算法,提升聚类效果以更好地挖掘微博用户相似兴趣集合。该方法融合了微博转发、评论、点赞等多...
  • 可变参数:是JDK1.5之后出现新特性; ...可变参数底层就是一个数组,根据传递参数个数不同,会创建不同长度数组,来存储这些参数 可传递参数个数,可以是0个(不传递),1,2,3...多个 ...
  • 在excle中的PERCENTRANK数学计算方法,数学含义,以及在python pandas中...计算方式: 集合中小于该数的数字个数/(集合包含的数字个数-1) 2.在pandas中如何实现呢? df['age'].rank()就可以返回PERCENTRANK值了~ ...
  • Ramsey理论是组合数学中一庞大而又丰富的领域,在集合论、逻辑学、分析以及代数学上具有极重要的应用.Ramsey数的求解是非常困难的,迄今为止只求出9Ramsey数的准确值.探讨了DNA生物分子超级计算在求解这一困难数学...
  • Java中四种遍历集合的方法

    万次阅读 2018-02-19 10:44:35
    Java中四种遍历集合的方法 迭代是集合中进行基本操作之一。基本上,迭代是从一到另一个集合 比如,你想在一班级中遍历所有学生打印出他们名字或找到在最近考试中最高分是谁。或者你想遍历一组数字...
  • Java中对于集合的遍历,我们常见4中遍历方式: 1.普通for循环; 2.foreach循环;...然后用以上4种方法计算每种使用时间。 代码如下: List<Integer> list=new ArrayList<Integer>(); for(...
  • 其实还可以使用List集合的RemoveAt方法来移除List集合元素,RemoveAt方法的方法签名为void RemoveAt(int index),index代表需要移除元素在List集合索引位置,List集合的索引位置从0开始计算。 例如有...
  • JAVA计算字符串中字符个数

    千次阅读 2020-06-08 20:39:20
    因为要计算字符串中字符个数,由于今天学习是Map集合,所以采用键值对的方法,创建一Hashmap,因为在Hashmap中键是不能够重复,所以用来记录出现字符,值value用来记录字符出现次数。 (2)遍历字符串,...
  • Bloom Filter计算方法

    2020-02-17 11:16:05
    如需要判断一个元素是不是在一个集合中,我们通常做法是把所有元素保存下来,然后通过比较知道它是不是在集合内,链表、树都是基于这种思路,当集合内元素个数的变大,我们需要的空间和时间都线性变大,检索速度也...
  • 对于一集合为元素栈,初始时栈为空。 输入命令有如下几种: PUSH:将空集{}压栈 DUP:将栈顶元素复制一份压入栈中 UNION:先进行两次弹栈,将获得的集合A和B取并集,将结果压栈 INTERS...
  • 多级汽液平衡过程的严格模型变量维高,用于构建优化命题时不易收敛且...结果表明,降维GM模型的计算变量由逐板模型的2377减少到34,同样平台下收敛时间由6136s缩短至1s左右,而关键组分纯度模拟与严格机理模型一致。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,458
精华内容 583
关键字:

集合个数的计算方法