假设我们有一个求集合的全部子集(包含集合自身)的需求,即有一个集合s,包含两个元素 <a,b>,则其全部的子集为<a,ab,b>.
不难求得,子集个数sn与原集合元素个数n之间的关系为:sn=2^n-1。
本文分别讲述两种实现方法:
一:位图法:
1)构造一个和集合一样大小的数组A,分别与集合中的某个元素对应,数组A中的元素只有两种状态:“1”和“0”,分别代表每次子集输出中集合中对应元素是否要输出,这样数组A可以看作是原集合的一个标记位图。
2)数组A模拟整数“加一”的操作,每“加一”之后,就将原集合中所有与数组A中值为“1”的相对应的元素输出。
设原集合为<a,b,c,d>,数组A的某次“加一”后的状态为[1,0,1,1],则本次输出的子集为<a,c,d>。
具体代码如下:set.sh
#!/bin/bash ## get the input set from the command line args inputstr=""; while getopts "s:" opt;do case $opt in s ) inputstr=$OPTARG ;; * ) echo "error" && exit;; esac done if [ "x$inputstr" == "x" ]; then echo "please input the set with -s parameter, with ',' as delimiter"; exit 1; fi inputarray=( ${inputstr//,/ } ) length=${#inputarray[*]}; ## init the bitmap and set all the element to "0" declare -a flagarray; for((i=0;i<=length;i++)) do flagarray[$i]="0"; done ## get the sub set until all the element is used while [ "${flagarray[$length]}" == "0" ] do ## calculate the subset's bitmap i=0; if [ "${flagarray[$i]}" == "0" ]; then flagarray[$i]="1"; else while [ "${flagarray[$i]}" == "1" ] do flagarray[$i]="0"; i=$((i+1)); done flagarray[$i]="1"; fi ## output one of the subset output=""; for((j=0;j<length;j++)) do if [ "${flagarray[$j]}" == "1" ]; then output="${output}${inputarray[$j]}," fi done echo ${output/%,/} done
3)时间复杂度:O(n*2^n)。其实,在遍历输出子集的过程中,可以对程序做进一步的优化。例如,在第m次迭代中,只需要遍历前k个元素,k=log2(m)+1。这样,不考虑数组模拟"加一"操作的话,总遍历次数为Sn=(n-2)*2^n+2,n>=2;Sn=1,n=1。虽然复杂度不变,但总运行时间会减少。
4)空间复杂度:该方法每次迭代都是独立进行,与上次迭代的结果没有任何关系。因此每次输出子集之后内存都可以被重复利用。只需要一个与原集合同样大小的数组,空间复杂度为O(n)。
二:递归迭代法:
1)采用递归迭代,具体过程如下,
设,原始集合s=<a,b,c,d>,子集结果为r:
第一次迭代:
r=<a>
第二次迭代:
r=<a ab b>
第三次迭代:
r=<a ab b ac abc bc c>
第四次迭代:
r=<a ab b ac abc bc c ad abd bd acd abcd bcd cd d>
每次迭代,都是上一次迭代的结果+上次迭代结果中每个元素都加上当前迭代的元素+当前迭代的元素。
具体代码如下:
#!/bin/bash ## get the input set from the command line args inputstr=""; while getopts "s:" opt;do case $opt in s ) inputstr=$OPTARG ;; * ) echo "error" && exit;; esac done if [ "x$inputstr" == "x" ]; then echo "please input the set with -s parameter, with ',' as delimiter"; exit 1; fi inputarray=( ${inputstr//,/ } ); length=${#inputarray[*]}; declare -a result; for((i=0;i<length-1;i++)) do reslen=${#result[*]}; for((j=0;j<reslen;j++)){ nextindex=$((j+reslen)); result[$nextindex]="${result[$j]},${inputarray[$i]}"; } reslen=${#result[*]}; result[$reslen]=${inputarray[$i]}; done for((i=0;i<${#result[@]};i++)) do echo "${result[$i]}"; echo "${result[$i]},${inputarray[$length-1]}" done echo "${inputarray[$length-1]}";
2)时间复杂度
根据上述过程,不难求的,第k次迭代的迭代次数为:2^k-1。n>=k>=1,迭代n次,总的遍历次数为:2^(n+1)-(2+n),n>=1。
则时间复杂都为O(2^n)。
3)空间复杂度
由于该算法,下一次迭代过程都需要上一次迭代的结果,而最后一次迭代之后就没有下一次了。因此假设原始集合有n个元素,则在迭代过程中,总共需要保存的子集个数为2^(n-1)-1,n>=1。但需要注意的是,这里之考虑了子集的个数,每个子集元素的长度都视为1,这点要注意。
总结:
比较上述两种算法,第一种可以看作是用时间换空间,而第二种是用空间换时间。
经过测试,当输入的原始集合元素为16个时。
执行耗时:
方法一:75秒
方法二:15秒
不过个人觉得如果输入集合较大,第二种算法就无法运行了。
相关推荐
试写一个递归算法实现求一个集合的所有子集。 算法设计: 给定一个非空的集合,用递归算法输出它的所有子集。 数据输入: 由文件input.txt 提供输入数据。文件第1行是集合中的元素个数,第2行是集合的元素序列(元素...
求一个集合的所有子集的C++实现
求集合的所有子集 数据结构 严蔚敏 求集合的所有子集 数据结构 严蔚敏 求集合的所有子集 数据结构 严蔚敏 求集合的所有子集 数据结构 严蔚敏 求集合的所有子集 数据结构 严蔚敏 求集合的所有子集 数据结构 严蔚敏
给定一个非空的集合,用递归算法输出它的所有子集。由文件input.txt 提供输入数据。文件第1行是集合中的元素个数,第2行是集合的元素序列(元素之间用空格分隔)。将计算出的所有子集分行输出到文件output.txt中。
C/C++ 求一个集合的子集,代码易懂,好用,谢谢下载
用于输出一个集合的所有子集,采用两种方法实现,值得一看!
回溯法求子集:输入n,输出集合{1,2,…,n}的所有子集(n) 回溯法求子集:输入n,输出集合{1,2,…,n}的所有子集(n)
java实验--求一个集合的子集,非递归实现。
求一个集合子集的算法示例, 用两种方法解,一种是基于回溯的递归求解,一种基于位域映射.
ARM指令子集--Thumb指令.pdf 学习资料 复习资料 教学资源
找到一个给定集合的所有子集,一个简单的小程序
求集合的所有子集问题,提供的全部代码。 使用递归算法!
Get subset of integers in a file named "source" ,which is in the same directory 即 求一个整数集合的子集,集合元素的个数不限, 采用读取文件的方式
GetSubSet是得到给定大小的所有子集,若要得到所有子集,只需从i=1,2,...,n分别调用。
该资源是求一组元素的所有子集的递归实现方法,代码用c++实现,简单明了而且有详细的说明。这是我自己写的,已经过测试,但难免会有疏漏,如发现有错误请跟我说,一同探讨改正。
下面小编就为大家带来一篇Java 通过位运算求一个集合的所有子集方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
输出n个数集合的所有子集 c++课程实验 eclipse 编写
程序设计算法, 集合所有子集下载 算法, 设计 数据 直接运行,
有两个实现方法: 1、一个是字符串,获取字符串最大递增子集 2、对象是list集合,获取list集合中最大递增子集 3、同理简单改正 也可以实现,连续相同字符串的最长子集