title: 子集生成算法
date: 2016-10-09 21:58:28
categories: 算法
tags: 窮舉
問題描述
??子集生成是暴力求解算法中比較經(jīng)典的問題，給出集合Ａ，求得相應(yīng)的子集，進(jìn)行打印。首先明確子集的定義，舉個例子，如果一個集合是
CodeCogsEqn (1).gif
那么生成的子集應(yīng)當(dāng)是空集，
CodeCogsEqn (2).gif
一般來說有三種方法，增量構(gòu)造法，位向量法，二進(jìn)制法。
算法思路
二進(jìn)制法思路
??在這里集合中的元素一定是存儲在數(shù)組中,所以可以看成數(shù)組中的元素和下標(biāo)對應(yīng)。那么此時集合中的元素就
CodeCogsEqn (3).gif
,轉(zhuǎn)化成的二進(jìn)制數(shù)，取值范圍也就是
CodeCogsEqn (4).gif
這2^n個數(shù)也就是整個集合的全排列，只需要判斷相應(yīng)位置二進(jìn)制表示，哪幾位是１，然后輸出相應(yīng)位置的元素即可，便得到了整個集合的子集結(jié)果。
二進(jìn)制法程序
下面給出子集生成算法的java代碼：
public class CreateSubset {
public static void get_subset(int n,int s,String str){
for(int i=0;i<n;i++)
{
int res = s&(1<<i);//看這2的n次方個數(shù)上哪些的位數(shù)是１。
if(res != 0)
System.out.print(str.charAt(i));//然后打印子集即可。
}
System.out.println();
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();//從控制臺得到字符串
int n = str.length();
for(int i=0;i<(1<<n);i++)//一共有2的n次方個子集
get_subset(n,i,str);
}
}
子集生成算法的Python代碼如下:
class Solution(object):
def get_subset(self,n,s,str):
for i in range(n):
res = s & (1 << i)
if res != 0:
print str[i],
print '\n'
def test(self):
str = raw_input('please input str:')
n = len(str)
lenth = 1 << n
for i in range(lenth):
self.get_subset(n,i,str)
