两种求集合所有子集的方法--Bash实现
假设我们有一个求集合的全部子集(包含集合自身)的需求，即有一个集合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 argsinputstr="";while getopts "s:" opt;do case $opt in s ) inputstr=$OPTARG ;; * ) echo "error" && exit;; esacdoneif [ "x$inputstr" == "x" ]; then echo "please input the set with -s parameter, with ',' as delimiter"; exit 1;fiinputarray=( ${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 usedwhile [ "${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/%,/}done3）时间复杂度：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 argsinputstr="";while getopts "s:" opt;do case $opt in s ) inputstr=$OPTARG ;; * ) echo "error" && exit;; esacdoneif [ "x$inputstr" == "x" ]; then echo "please input the set with -s parameter, with ',' as delimiter"; exit 1;fiinputarray=( ${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]};donefor((i=0;i<${#result[@]};i++))do echo "${result[$i]}"; echo "${result[$i]},${inputarray[$length-1]}"doneecho "${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秒
?
不过个人觉得如果输入集合较大，第二种算法就无法运行了。