精华内容
下载资源
问答
  • C/C++ 求一个集合子集,代码易懂,好用,谢谢下载
  • 今天小编就为大家分享一篇Python 实现求一个集合所有子集的示例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 求一个集合的所有子集问题

    万次阅读 多人点赞 2014-06-15 21:44:56
    一个包含n个元素的集合,它的所有子集。比如集合A= {1,2,3}, 它的所有子集是: { {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, @}(@表示空集)。 这种问题一般有两种思路,先说说第一种,递归。递归肯定要...

    一个包含n个元素的集合,求它的所有子集。比如集合A= {1,2,3}, 它的所有子集是:

     

    { {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, @}(@表示空集)。

     

    这种问题一般有两种思路,先说说第一种,递归。递归肯定要基于一个归纳法的思想,这个思想用到了二叉树的遍历,如下图所示:

     

     

    可以这样理解这张图,从集合A的每个元素自身分析,它只有两种状态,或是某个子集的元素,或是不属于任何子集,所以求子集的过程就可以看成对每个元素进行“取舍”的过程。上图中,根结点是初始状态,叶子结点是终结状态,该状态下的8个叶子结点就表示集合A的8个子集。第i层(i=1,2,3…n)表示已对前面i-1层做了取舍,所以这里可以用递归了。整个过程其实就是对二叉树的先序遍历。

     

    根据上面的思想,首先需要一个结构来存储元素,这个”取舍”过程,其实就是在线性结构中的增加和删除操作,很自然考虑用链式的存储结构,所以我们先来实现一个链表:

     

    typedef struct  LNode
    {
    	int data;
    	LNode *next;
    }LinkList;
    
    //建立一个链表,你逆向输入n个元素的值
    int listCreate(LinkList *srcList, int number)
    {
    	LinkList *pTemp;
    	int i = 0;
    	srcList->next = NULL;
    	srcList->data = 0;
    
    	for (i = number; i > 0; --i)
    	{
    		pTemp = (LinkList *)malloc(sizeof(LNode));
    		pTemp->data = i+20;//随便赋值
    		pTemp->next = srcList->next;
    		srcList->next = pTemp;
    	}
    	return 0;
    }
    
    //销毁一个链表
    int listDestroy(LinkList *srcList)
    {
    	if (!srcList || !srcList->next)
    	{
    		return 0;
    	}
    
    	LinkList *p1 = srcList->next;
    	LinkList *p2 = p1->next;
    
    	do
    	{
    		free(p1);
    		p1 = p2;
    		if (p2 != NULL)
    		{
    			p2 = p2->next;
    		}
    	}while (p1);
    	return 0;
    }
    
    //插入操作
    //在strList第nIndex之前插入数据data
    //nIndex最小为1
    int listInsert(LinkList *srcList, int nIndex, int data)
    {
    	LinkList *pStart = srcList;
    	int j = 0;
    	if (nIndex < 1)
    	{
    		return 0;
    	}
    	while((pStart) && (j < nIndex-1))
    	{
    		pStart = pStart->next;
    		j++;
    	}
    	if ((!pStart) || (j > nIndex-1))
    	{
    		return -1;//出错
    	}
    
    	LinkList *temp = (LinkList *)malloc(sizeof(LNode));
    	temp->data = data;
    	temp->next = pStart->next;
    	pStart->next = temp;
    	return 0;
    }
    
    //删除操作
    //strList第nIndex位置的结点删除,并通过data返回被删的元素的值
    //通常情况下返回的这个值是用不到的,不过这里也保留备用
    int listDelete(LinkList *srcList, int nIndex, int *data)
    {
    	LinkList *pStart = srcList;
    	int j = 0;
    	if (nIndex < 1)
    	{
    		return 0;
    	}
    
    	while((pStart) && (j < nIndex-1))
    	{
    		pStart = pStart->next;
    		j++;
    	}
    	if ((!pStart) || (j > nIndex-1))
    	{
    		return -1;//出错
    	}
    	LinkList *pTemp = pStart->next;
    	pStart->next = pTemp->next;
    	*data = pTemp->data;
    	free(pTemp);
    
    }
    

     

     

    有了这个链表,递归算法实现起来就很容易了:

     

    //求冥集,nArray是存放n个元素的数组
    //首次调用i传1,表示已对前面i-1个元素做了处理
    void GetPowerSet(int nArray[], int nLength, int i, LinkList *outPut)
    {
    	int k = 0;
    	int nTemp = 0;
    	if (i >= nLength)
    	{
    		printList(*outPut);
    	}
    	else
    	{
    		k = listLength(outPut);
    		listInsert(outPut, k+1, nArray[i]);
    		GetPowerSet(nArray, nLength, i+1, outPut);
    		listDelete(outPut, k+1, &nTemp);
    		GetPowerSet(nArray, nLength, i+1, outPut);
    	}
    
    }

     

     

     

     

     

    还有一种思想比较巧妙,可以叫按位对应法。如集合A={a,b,c},对于任意一个元素,在每个子集中,要么存在,要么不存在

    映射为子集:

    (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)->@(@表示空集)

    观察以上规律,与计算机中数据存储方式相似,故可以通过一个整型数与集合映射...000 ~ 111...111(表示有,表示无,反之亦可),通过该整型数逐次增可遍历获取所有的数,即获取集合的相应子集。

    实现起来很容易:

     

    void GetPowerSet2(int nArray[], int nLength)
    {
    	int mark = 0;
    	int i = 0;
    	int nStart = 0;
    	int nEnd = (1 << nLength) -1;
    	bool bNullSet = false;
    
    	for (mark = nStart; mark <= nEnd; mark++)
    	{
    		bNullSet = true;
    		for (i = 0; i < nLength; i++)
    		{
    			if (((1<<i)&mark) != 0) //该位有元素输出
    			{
    				bNullSet = false;
    				printf("%d\t", nArray[i]);
    			}
    		}
    		if (bNullSet) //空集合
    		{
    			printf("@\t");
    		}
    		printf("\n");
    	}
    }

     

     

     

     

     

    分析代码可以得出它的复杂度是O(n*2^n)。

     

    代码下载地址:

    https://github.com/pony-maggie/PowerSetDemo

    http://download.csdn.net/detail/pony_maggie/7499161

    展开全文
  • 求一个集合所有子集的Python实现

    万次阅读 2017-09-06 20:39:56
    收集整理求一个集合的所有子集的Python实现方法,以供大家参考。

    方法一:回归实现

    def PowerSetsRecursive(items):
        """Use recursive call to return all subsets of items, include empty set"""
        
        if len(items) == 0:
            #if the lsit is empty, return the empty list
            return [[]]
        
        subsets = []
        first_elt = items[0] #first element
        rest_list = items[1:]
        
        #Strategy:Get all subsets of rest_list; for each of those subsets, a full subset list
        #will contain both the original subset as well as a version of the sebset that contains the first_elt
        
        for partial_sebset in PowerSetsRecursive(rest_list):
            subsets.append(partial_sebset)
            next_subset = partial_sebset[:] +[first_elt]
            subsets.append(next_subset)
        return subsets
    
    
    def PowerSetsRecursive2(items):
        # the power set of the empty set has one element, the empty set
        result = [[]]
        for x in items:
            result.extend([subset + [x] for subset in result])
        return result 



    
    方法二:二进制法
    

    def PowerSetsBinary(items):
        #generate all combination of N items
        N = len(items)
        #enumerate the 2**N possible combinations
        for i in range(2**N):
            combo = []
            for j in range(N):
                #test jth bit of integer i
                if(i >> j ) % 2 == 1:
                    combo.append(items[j])
            yield combo
    
    

    会陆续整理出其他的方法,当然,也欢迎在评论区留言。。。。。。

    展开全文
  • 令S是n元素的集合,它的幂集是它所有子集集合。例如,如果S={a,b,c},那么powerset{S}={{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}。写出递归函数实现powerset{S} #include <iostream> using namespace ...

    系列文章目录

    前言

    《数据结构基础》c语言版 第2版,Ellis Horowitz著,朱仲涛译
    1.3节,page14,习题12

    一、题目描述

    令S是n个元素的集合,它的幂集是它所有子集的集合。例如,如果S={a,b,c},那么powerset{S}={{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}。写出递归函数实现powerset{S}

    二、c++代码

    1.引入库

    代码如下:

    #include <iostream>
    using namespace std;
    
    void powerset(char *array,int a[],int index,int n)
    {
        if(index==n)
        {
            printf("{");
            for(int i=0;i<n;i++)
            {
                if(a[i])
                    printf("%c ",array[i]);
            }
            printf("},");
        } else
        {
            a[index]=0;
            powerset(array,a,index+1,n);
            a[index]=1;
            powerset(array,a,index+1,n);
        }
    }
    
    int main()
    {
        char arr[3]={'a','b','c'};
        int aa[3];
        printf("{");
        powerset(arr,aa,0,sizeof(arr));
        printf("}");
        return 0;
    }
    

    总结

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

    千次阅读 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次方。

     

    展开全文
  • 求一个集合的所有子集

    千次阅读 2019-03-20 18:33:15
    求一个集合的所有结合,例如集合{A,B,C}的所有子集为:{},{A,B,C},{A,B},{A,C},{B,C},{A},{B},{C}。 思路 实际上求子集问题是一个经典的DFS,每一次选择某个元素时,都会面临两个选择,一个是不选一个是选: 第一...
  • 题目:求一个数组的所有子集。 如int a[]={1,2,3}.其子集为有2^n=8 它们是:{},1,2,3,12,13,23,123 分析: 我们可以使用二进制位标记来做。子集中有某个字符用1标记,不存在用0标记,则: 000 {} 001 c 011 bc...
  • 题目描述: 给定组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明:解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3], ...
  • 求一个集合的所有子集问题实现

    千次阅读 2016-12-08 22:00:02
    已知N个大于0的整数构成一个集合,即{1,2,3,……,N},其所有的非空且元素不相邻的子集,计算所有子集的乘积的平方的和。 例如:集合{1,2,3,4},其所有非空不相邻子集有{1},{2},{3},{4},{1,3},{1,4...
  • 计算一个集合子集

    2016-03-05 16:11:37
    用递归的方法计算出集合子集
  • Java没有自带的求一个集合的所有子集的方法,我们可以通过集合子集规律来一个集合的所有子集等于2^该集合的长度。比如{c,b,a}的长度为3,这个集合子集就有8个。 这句话看起来很简单,但同时也隐含着高深...
  • 有这样的两个集合: string[] bigArr = new string[] { "a", "b", "c" };string[] smallArr = new string[] { "a", "b"}; 现在需要判断smallArr是否是bigArr的子集。只要拿着bigArray和smallArr比较,差集,...
  • 递归求集合子集

    2018-03-27 20:14:04
    那个紫书上求子集只是1~n,并不是指定集合a的子集,其实很简单,一个BFS递归一下,用vector保存这个集合,有两个状态:1.取a[i]放vector中;2.不取a[i] 直接上代码: #include&lt;cstdio&gt; #include&...
  • 在处理前要对传入数组排序,不然返回的子集虽然对但和系统的顺序不一样导致不能Acceptedjava代码的种递归的方式public class Solution { /** * @param nums: A set of numbers * @return: A list of lists */ ...
  • 求一个集合的所有子集(java实现)

    千次阅读 2015-09-25 14:07:22
    求一个集合的所有子集表示从一个集合当中,任取任意项或不取,所能得到的所有结果,比如有一个集合{a,b,c,d},那么{a,b}, {b, d}等都是它的子集,空集也是它的子集一个具有n 个元素的集合,它的子集共有2^n个,...
  • python求集合子集子集个

    千次阅读 2019-05-22 18:07:45
    集合A有n元素,则集合A的子集个数为2n,且有2n-1子集,2n-2非空真子集。 用python中的itertools.combinations(iterable, r)实现了一下: r: 某特定长度的子序列 另玩了下combinations_with_replacement...
  • 求一个集合的所有子集 Python实现 #!/usr/bin/env python3 # -*- coding: utf-8 -*- """ Created on Sat Jun 23 16:59:07 2018 @author: luogan """ def PowerSetsBinary...
  • 求一个集合的所有子集(c++实现)

    千次阅读 2020-01-12 15:14:48
    求一个集合的所有子集就是很简单的一道关于组合的题目,是一个集合内的元素的任意组合。一接触这类的题目,感觉头都大,让我找出三个数的任意组合我都担心找不全,更别提更多的数的组合了。在网上查了解决方法,发现...
  • 通常判断集合子集一般都是使用issubset,但是今天在看到一段代码:判断一个权限列表是否为另一个权限列表的子集时看到用到了相减的方法,感觉很有意思,所以做个记录 x = {3, 4} y = {3, 4, 5, 6} if 0 == len...
  • 求一个集合的所有子集(c语言)

    千次阅读 2020-07-24 19:02:59
    如果一个集合的元素个数为n,则每个元素都有存在或不存在两种情况,n个元素一共2^n种情况,因此元素个数为n的集合一共有2的n次方个子集。 算法1: 利用二进制的思想 如 0110 1001,0表示该数组位置不选,1表示选中。...
  • 回溯法求一个集合的所有子集Description: 描述: This is a standard interview problem to find out the subsets of a given set of numbers using backtracking. 这是一个标准的面试问题,它使用回溯来找出给定...
  • 求集合子集

    2015-07-07 20:34:27
    描述:求一个集合的所有子集,如集合{1,2,3},则它的子集为 {},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}。 解决:集合的所有子集的个数为2^n,时间复杂度为2^n,空间复杂度做到n, 用二进制来表示子集...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 134,940
精华内容 53,976
关键字:

一个集合的子集怎么求