精华内容
下载资源
问答
  • 集合的所有子集的算法

    千次阅读 2017-09-07 20:52:42
    集合的所有子集的算法 对于任意集合A,元素个数为n(空集n=0),其所有子集的个数为2^n个 如集合A={a,b,c},其子集个数为8;对于任意一个元素,在每个子集中, 要么存在,要么不存在,对应关系是: a->1或a->0 ...

    转载自:http://blog.csdn.net/yzl20092856/article/details/39995085

    求集合的所有子集的算法

    对于任意集合A,元素个数为n(空集n=0),其所有子集的个数为2^n个

    如集合A={a,b,c},其子集个数为8;对于任意一个元素,在每个子集中,

    要么存在,要么不存在,对应关系是:

    a->1或a->0

    b->1或b->0

    c->1或c->0

    映射为子集:

    (a,b,c)

    (1,1,1)->(a,b,c)

    (1,1,0)->(a,b  )

    (1,0,1)->(a,  c)

    (1,0,0)->(a     )

    (0,1,1)->(  b,c)

    (0,1,0)->(  b   )

    (0,0,1)->(     c)

    (0,0,0)->@(@表示空集)

    算法(1):

    观察以上规律,与计算机中数据存储方式相似,故可以通过一个整型数(int)与

    集合映射000...000 ~ 111...111(0表示有,1表示无,反之亦可),通过该整型数

    逐次增1可遍历获取所有的数,即获取集合的相应子集。

    在这里提一下,使用这种方式映射集合,在进行集合运算时,相当简便,如

    交运算对应按位与&,{a,b,c}交{a,b}得{a,b}<--->111&110==110

    并运算对应按位或|

    差运算对应&~

    算法(2):

    设函数f(n)=2^n (n>=0),有如下递推关系f(n)=2*f(n-1)=2*(2*f(n-2))

    由此可知,求集合子集的算法可以用递归的方式实现,对于每个元素用一个映射列表marks,标记其

    在子集中的有无

    很显然,在集合元素个数少的情况下,算法(1)优于算法(2),因为只需通过加法运算,便能映射

    出子集,而算法(2)要递归调用函数,速度稍慢。但算法(1)有一个严重缺陷,集合的个数不能大于在

    计算机中一个整型数的位数,一般计算机中整型数的为32位。对于算法(2)就没这样限制。

     

    1.	template<class T>  
    2.	void print(T a[],int mark,int length)    
    3.	{    
    4.	    bool allZero=true;    
    5.	    int limit=1<<length;    
    6.	    for(int i=0;i<length;++i)    
    7.	    {    
    8.	        if(((1<<i)&mark)!=0)      //mark第i+1位为1,表示取该元素    
    9.	        {    
    10.	            allZero=false;    
    11.	            cout<<a[i]<<" ";    
    12.	        }    
    13.	    }    
    14.	    if(allZero==true)    
    15.	    {    
    16.	        cout<<"@";    
    17.	    }    
    18.	    cout<<endl;    
    19.	}  
    20.	  
    21.	template<class T>  
    22.	void subset(T a[],int length)    
    23.	{    
    24.	    if(length>31) return;    
    25.	    int lowFlag=0;                  //对应000...000    
    26.	    int highFlag=(1<<length)-1;       //对应111...111    
    27.	    for(int i=lowFlag;i<=highFlag;++i)    
    28.	    {    
    29.	        print(a,i,length);    
    30.	    }  
    31.	  
    32.	}  
    
    
    算法二:

    template<class T>    
    void print(T a[],bool marks[],int length)    
    {    
        bool allFalse=true;    
        for(int i=0;i<length;++i)    
        {    
            if(marks[i]==true)    
            {    
                allfalse=false;    
                cout<<a[i]<<"  ";    
            }    
        }    
        if(allFalse==true)    
        {    
            cout<<"@";    
        }    
        cout<<endl;  
      
    }  
      
    template<class T>  
    void subset(T a[],bool marks[],int m,int n,int length)    
    {    
        if(m>n)    
        {    
            print(a,marks,length);    
        }    
        else    
        {    
            marks[m]=true;    
            subset(a,marks,m+1,n,length);   
            marks[m]=false;    
            subset(a,marks,m+1,n,length);   
        }  
      
    }  


    展开全文
  • 集合的所有子集的算法

    千次阅读 2014-10-11 15:30:14
    集合的所有子集的算法对于任意集合A,元素个数为n(空集n=0),其所有子集的个数为2^n个如集合A={a,b,c},其子集个数为8;对于任意一个元素,在每个子集中,要么存在,要么不存在,对应关系是:a->1或a->0b->1或b->...

    转自:http://plutoblog.iteye.com/blog/976218

    求集合的所有子集的算法

    对于任意集合A,元素个数为n(空集n=0),其所有子集的个数为2^n个

    如集合A={a,b,c},其子集个数为8;对于任意一个元素,在每个子集中,

    要么存在,要么不存在,对应关系是:

    a->1或a->0

    b->1或b->0

    c->1或c->0

    映射为子集:

    (a,b,c)

    (1,1,1)->(a,b,c)

    (1,1,0)->(a,b   )

    (1,0,1)->(a,   c)

    (1,0,0)->(a      )

    (0,1,1)->(   b,c)

    (0,1,0)->(   b   )

    (0,0,1)->(      c)

    (0,0,0)->@ (@表示空集)

    算法(1):

    观察以上规律,与计算机中数据存储方式相似,故可以通过一个整型数(int)与

    集合映射000...000 ~ 111...111(0表示有,1表示无,反之亦可),通过该整型数

    逐次增1可遍历获取所有的数,即获取集合的相应子集。

    在这里提一下,使用这种方式映射集合,在进行集合运算时,相当简便,如

    交运算对应按位与&,{a,b,c}交{a,b}得{a,b}<--->111&110==110

    并运算对应按位或|,

    差运算对应&~。

    算法(2):

    设函数f(n)=2^n (n>=0),有如下递推关系f(n)=2*f(n-1)=2*(2*f(n-2))

    由此可知,求集合子集的算法可以用递归的方式实现,对于每个元素用一个映射列表marks,标记其

    在子集中的有无

    很显然,在集合元素个数少的情况下,算法(1)优于算法(2),因为只需通过加法运算,便能映射

    出子集,而算法(2)要递归调用函数,速度稍慢。但算法(1)有一个严重缺陷,集合的个数不能大于在

    计算机中一个整型数的位数,一般计算机中整型数的为32位。对于算法(2)就没这样限制。

    -----------------------------------------------------------------------------------------

    算法(1,取低位到高位码段作为映射列表

    template<class T>
    
    void print(T a[],int mark,int length)
    
    {
    
    	bool allZero=true;
    
    	int limit=1<<length;
    
    	for(int i=0;i<length;++i)
    
    	{
    
    		if(((1<<i)&mark)!=0)		//mark第i+1位为1,表示取该元素
    
    		{
    
    			allZero=false;
    
    			cout<<a[i]<<" ";
    
    		}
    
    	}
    
    	if(allZero==true)
    
    	{
    
    		cout<<"@";
    
    	}
    
    	cout<<endl;
    
    }
    
    template<class T>
    
    void subset(T a[],int length)
    
    {
    
    	if(length>31) return;
    
    	int lowFlag=0;					//对应000...000
    
    	int highFlag=(1<<length)-1;		//对应111...111
    
    	for(int i=lowFlag;i<=highFlag;++i)
    
    	{
    
    		print(a,i,length);
    
    	}
    
    }


    -----------------------------------------------------------------------------------------

    算法(2)

    template<class T>
    
    void print(T a[],bool marks[],int length)
    
    {
    
    	bool allFalse=true;
    
    	for(int i=0;i<length;++i)
    
    	{
    
    		if(marks[i]==true)
    
    		{
    
    			allfalse=false;
    
    			cout<<a[i]<<"  ";
    
    		}
    
    	}
    
    	if(allFalse==true)
    
    	{
    
    		cout<<"@";
    
    	}
    
    	cout<<endl;
    
    }
    
    template<class T>
    
    void subset(T a[],bool marks[],int m,int n,int length)
    
    {
    
    	if(m>n)
    
    	{
    
    		print(a,marks,length);
    
    	}
    
    	else
    
    	{
    
    		marks[m]=true;
    
    		subset(a,marks,m+1,n,length);
    
    		marks[m]=false;
    
    		subset(a,marks,m+1,n,length);
    
    	}
    
    }


    展开全文
  • 集合的所有子集的算法(C++)

    千次阅读 2011-03-26 20:01:11
    集合的所有子集的算法 对于任意集合A,元素个数为n(空集n=0),其所有子集的个数为2^n个 如集合A={a,b,c},其子集个数为8;对于任意一个元素,在每个子集中, 要么存在,要么不存在,对应关系是: a-&gt;...

     

    求集合的所有子集的算法

    对于任意集合A,元素个数为n(空集n=0),其所有子集的个数为2^n个

    如集合A={a,b,c},其子集个数为8;对于任意一个元素,在每个子集中,

    要么存在,要么不存在,对应关系是:

    a->1或a->0

    b->1或b->0

    c->1或c->0

    映射为子集:

    (a,b,c)

    (1,1,1)->(a,b,c)

    (1,1,0)->(a,b   )

    (1,0,1)->(a,   c)

    (1,0,0)->(a      )

    (0,1,1)->(   b,c)

    (0,1,0)->(   b   )

    (0,0,1)->(      c)

    (0,0,0)->@ (@表示空集)

    算法(1):

    观察以上规律,与计算机中数据存储方式相似,故可以通过一个整型数(int)与

    集合映射000...000 ~ 111...111(0表示有,1表示无,反之亦可),通过该整型数

    逐次增1可遍历获取所有的数,即获取集合的相应子集。

    在这里提一下,使用这种方式映射集合,在进行集合运算时,相当简便,如

    交运算对应按位与&,{a,b,c}交{a,b}得{a,b}<--->111&110==110

    并运算对应按位或|,

    差运算对应&~。

    算法(2):

    设函数f(n)=2^n (n>=0),有如下递推关系f(n)=2*f(n-1)=2*(2*f(n-2))

    由此可知,求集合子集的算法可以用递归的方式实现,对于每个元素用一个映射列表marks,标记其

    在子集中的有无

    很显然,在集合元素个数少的情况下,算法(1)优于算法(2),因为只需通过加法运算,便能映射

    出子集,而算法(2)要递归调用函数,速度稍慢。但算法(1)有一个严重缺陷,集合的个数不能大于在

    计算机中一个整型数的位数,一般计算机中整型数的为32位。对于算法(2)就没这样限制。

    -----------------------------------------------------------------------------------------

    算法(1,取低位到高位码段作为映射列表

    template<class T>

    void print(T a[],int mark,int length)

    {

    bool allZero=true;

    int limit=1<<length;

    for(int i=0;i<length;++i)

    {

    if(((1<<i)&mark)!=0) //mark第i+1位为1,表示取该元素

    {

    allZero=false;

    cout<<a[i]<<" ";

    }

    }

    if(allZero==true)

    {

    cout<<"@";

    }

    cout<<endl;

    }

    template<class T>

    void subset(T a[],int length)

    {

    if(length>31) return;

    int lowFlag=0; //对应000...000

    int highFlag=(1<<length)-1; //对应111...111

    for(int i=lowFlag;i<=highFlag;++i)

    {

    print(a,i,length);

    }

    }

    -----------------------------------------------------------------------------------------

    算法(2)

    template<class T>

    void print(T a[],bool marks[],int length)

    {

    bool allFalse=true;

    for(int i=0;i<length;++i)

    {

    if(marks[i]==true)

    {

    allfalse=false;

    cout<<a[i]<<"  ";

    }

    }

    if(allFalse==true)

    {

    cout<<"@";

    }

    cout<<endl;

    }

    template<class T>

    void subset(T a[],bool marks[],int m,int n,int length)

    {

    if(m>n)

    {

    print(a,marks,length);

    }

    else

    {

    marks[m]=true;

    subset(a,marks,m+1,n,length);

    marks[m]=false;

    subset(a,marks,m+1,n,length);

    }

    }

    展开全文
  • private static ArrayList SubSet(ArrayList set) { ArrayList subSet = new ArrayList(); ArrayList itemSet = new ArrayList(); int num = 1 &lt;&lt; set.Count;...for (int i ...
    private static ArrayList SubSet(ArrayList set) 
    {
    ArrayList subSet = new ArrayList();

    ArrayList itemSet = new ArrayList();

    int num = 1 << set.Count;

    int bit;
    int mask = 0; ;
    for (int i = 0; i < num;i++ )
    {
    itemSet = new ArrayList();
    for (int j = 0; j < set.Count; j++)
    {
    mask = 1 << j;
    bit = i & mask;
    if (bit >0) {

    itemSet.Add(set[j]);

    }
    }
    if (itemSet.Count > 0)
    {
    subSet.Add(itemSet);
    }


    }



    return subSet;
    }
    展开全文
  • 算法篇:输出集合的所有子集

    千次阅读 2014-04-08 11:19:02
    题目描述:输出含有n个元素集合的所有子集。例如,三个元素{a,b,c}的所有子集是:{},{a},{b},{c},{a,c},{ac},{b,c},{a,b,c}.输入:abc输出:cbabacaacbbcnull解题思路:递归思路:* 例如:对于集合{a,b,c}来说,我们...
  • Python算法——求集合的所有子集

    千次阅读 2019-08-11 17:32:05
    有一个集合,求其全部子集(包含集合自身)。例如集合[1,2,3]其全部子集为:<∅,1,2,12,3,13,23,123> 分析: 方法一:位图法 ①使用两层循环,外层循环为子集个数,对于集合长度为N,子集个数为。外层...
  • 转自输出一个集合的所有子集算法) 时间复杂度很显然,最少也是2^n,空间复杂度,是n,代码比较简单(每个元素要么在子集中,要么不在,用 j 的二进制形式的每一位代表数组a中对应的位置的元素是否在子...
  • 集合的所有子集

    2015-09-20 01:32:41
    给定一个非空的集合,用递归算法输出它的所有子集。由文件input.txt 提供输入数据。文件第1行是集合中的元素个数,第2行是集合的元素序列(元素之间用空格分隔)。将计算出的所有子集分行输出到文件output.txt中。
  • datetime.datetime.now() res=PowerSetsRecursive3(a) end_t = datetime.datetime.now() elapsed_sec = (end_t - start_t).total_seconds() print(elapsed_sec) print(len(res)) 这个取了20个数字的集合所有子集个...
  • 试写一个递归算法实现求一个集合的所有子集算法设计: 给定一个非空的集合,用递归算法输出它的所有子集。 数据输入: 由文件input.txt 提供输入数据。文件第1行是集合中的元素个数,第2行是集合的元素序列(元素...
  • 输出集合所有子集的算法

    千次阅读 2009-06-08 20:49:00
    算法描述:把求子集运算转换为组合问题。假设集合中包含N个元素, 子集合数 = C(N, 0) + C(N, 1) + ... + C(N, N-1) + C(N, N),对于任一...因此,求子集合就转换成了罗列所示可能组合的算法子集合数 = 2^n。 void
  • 集合子集的算法

    千次阅读 2012-07-31 23:16:19
    集合的所有子集的算法(C++) fr:http://plutoblog.iteye.com/blog/976218   求集合的所有子集的算法 对于任意集合A,元素个数为n(空集n=0),其所有子集的个数为2^n个 如集合A={a,b,c},其子集...
  • 算法-求集合所有子集

    2020-05-03 15:27:11
    问题:求集合所有子集。 下面给出两个思路的递归和非递归解法,用python实现。 方法一 a的子集可以分为两部分: ...总结:a[0:n]所有子集 = a[1:n]的所有子集(不含a[0]) + {a[0] + a[1:n]的所有子集(含...
  • {1,2,3} 的所有排列组合方式 {1,2,3} {1,23} {12,3} {13,2} {123} 请大家给个想法 或者 算法实现
  • Java 没有自带的求一个集合的所有子集的方法,我们可以通过集合的子集规律来求。 思路: 对集合中所有元素进行标记,0表示未选中,1表示选中。 示例: 集合{1,2,3,4},长度为4,则 0000表示一个都不选,0001...
  • 打印集合的所有子集

    千次阅读 2014-03-12 14:43:30
    怎样将所有的子集打印出来?最简单O(N^3)算法不难想到,但是太过于朴素,应该还有更巧方法。 我们已知,一个元素个数为n的集合,其子集个数为2^n个。比如set { 1, 2 },含有两个元素,一共有四个子集,分别为{ ...
  • 求一个集合的幂集我们如果用编程的思维来思考的话想到的有dfs暴力搜索,就是把集合的每一项两种选择进行枚举。除了暴力我们有没有办法直接求解呢? 我们仔细观察一下有n个元素的集合和n-1个元素的集合我们知道数学...
  • 集合的所有子集问题,提供的全部代码。 使用递归算法
  • 题目 思路 一开始的思路像是数学的排列组合,通过切片生成子集,但是考虑了一下还是比较复杂,在集合比较长的时候很难去设计算法。 正确的思路: ...从上往下看,集合每增加一个元素,新的子集的前一
  • 程序设计算法集合所有子集下载 算法, 设计 数据 直接运行,
  • 前言: 对任意集合A,它有2^n个子集(n为集合A中的元素的个数),为什么...采用递归方式,对于求含有n个元素的集合的子集,递归求解它的n-1个元素的所有子集存于结果集中,再赋复制一份结果集出来,为复制出来的结果集
  • Python程序员面试算法宝典---解题总结: 第4章 数组 4.14 如何求集合的所有子集 题目: 有一个集合,求其全部子集(包含集合自身),给定一个集合s,它包含两个 元素<a, b>,则其全部的子集为<a, ab, b>。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 676
精华内容 270
关键字:

集合的所有子集的算法