算法 集合的所有子集 全排列

Question

{1,2,3}的所有排列组合方式{{1},{2},{3}}{{1},{2,3}}{{1,2},{3}}{{1,3},{2}}{{123}}请大家给个想法或者算法实现

Answer 1

publicList>>allSubsetPermutation(int[]nums){
if(nums==null||nums.length==0)
returnnull;
Queue>>q=newLinkedList<>();
q.add(newLinkedList<>());
for(intn:nums){
intsize=q.size();
while(size-->0){
List>list=q.poll();
for(inti=0;iList>l=deepClone(list);
l.get(i).add(n);
q.offer(l);
}
list.add(newLinkedList<>(Arrays.asList(n)));
q.offer(list);
}
}
returnnewLinkedList<>(q);
}
privateList>deepClone(List>list){
List>l=newLinkedList<>();
for(Listli:list)
l.add(newLinkedList<>(li));
returnl;
}
@Test
publicvoidtest(){
List>>l=null;
l=allSubsetPermutation(newint[]{1});
l=allSubsetPermutation(newint[]{1,2});
l=allSubsetPermutation(newint[]{1,2,3});
l=allSubsetPermutation(newint[]{1,2,3,4});
return;
}
                            

Answer 2

这个我想到高中的排列组合，用的是隔板法(不太记得是不是叫这个)。比如，隔板是说在1|2|3|4数字中间放的分隔板。分成一个集合，不用隔板分成两个集合，放一个隔板，共C(n-1,1),比如{1|234}{12|34}{123|4}分成k个集合，放k-1个隔板，共C(n-1,k-1)种。
然后想如何实现隔板，给隔板编号1,2,...,n-1于是每次放k个隔板意味着从n-1个数中取出k个数字，就是组合数，可以用回溯遍历出来
seq[]放k的数字
seq[]=-1表示这个位置没有数字
DFS(index){
if(index==k){print();return;}
for(inti=1;i<=n-1;++i){
if(seq[index]==-1){
seq[index]=i;//
DFS(index+1)
seq[index]=-1
}
}
}
print(){
intindex=0;
for(inti=1;i<=n;++i){
printf(i);
if(i==seq[index]){index++;print(|)}
}
}
DFS(1)
讲的好，如果不存储全部的子集的话，每次维护/保存当前i的子集的序列，每次加一个i+1时，只需要输出i，和将i加到当前序列里面就可以了。
DFS(intnum){
print({num});
for(inti=0;iseq[i].add(num);//把num加入当前队列
print({);//便于显示观看
for(intj=0;jprinf(seq[i][j]);
prinf(});//便于显示观看
}
DFS(num+1);
}
如果不存储全部的子集的话,只需要复制seq，再添加num到其中一个seq中去即可，再加一个{num}。
咦？其实这个也可以直接一个循环，不用DFS还要浪费栈，因为num是从1到n没有变化的呀！
for(intnum=1;num<=n;++num)
{
print({num});
for(inti=0;iseq[i].add(num);//把num加入当前队列
print({);//便于显示观看
for(intj=0;jprinf(seq[i][j]);
prinf(});//便于显示观看
}
}