打印列表的所有可能子集

我有一个元素列表（1,2,3），我需要获取该列表的超集（powerset）（没有重复元素）。 所以基本上我需要创建一个列表列表，如下所示：

{1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3} 

实现这一目标的最佳方式是什么（简单>效率在这种情况下，列表不会很大）？ 最好是在Java中，但任何语言的解决方案都是有用的。

Answer 1

使用位掩码：

 int allMasks = (1 << N); for (int i = 1; i < allMasks; i++) { for (int j = 0; j < N; j++) if ((i & (1 << j)) > 0) //The j-th element is used System.out.print((j + 1) + " "); System.out.println(); } 

以下是所有位掩码：

 1 = 001 = {1} 2 = 010 = {2} 3 = 011 = {1, 2} 4 = 100 = {3} 5 = 101 = {1, 3} 6 = 110 = {2, 3} 7 = 111 = {1, 2, 3} 

你知道二进制中第一位是最右边的。

Answer 2

 import java.io.*; import java.util.*; class subsets { static String list[]; public static void process(int n) { int i,j,k; String s=""; displaySubset(s); for(i=0;i 

Answer 3

基于Petar Minchev解决方案的Java解决方案 –

 public static List> getAllSubsets(List input) { int allMasks = 1 << input.size(); List> output = new ArrayList>(); for(int i=0;i sub = new ArrayList(); for(int j=0;j 0) { sub.add(input.get(j)); } } output.add(sub); } return output; } 

Answer 4

我注意到答案集中在字符串列表上。 因此，我决定分享更多通用答案。 希望它会有用。 （Soultion基于我发现的另一种解决方案，我将它与一般的算法结合起来。）

 /** * metod returns all the sublists of a given list * the method assumes all object are different * no matter the type of the list (generics) * @param list the list to return all the sublist of * @param  * @return list of the different sublists that can be made from the list object */ public static  List>getAllSubLists(Listlist) { ListsubList; List>res = new ArrayList<>(); List> indexes = allSubListIndexes(list.size()); for(List subListIndexes:indexes) { subList=new ArrayList<>(); for(int index:subListIndexes) subList.add(list.get(index)); res.add(subList); } return res; } /** * method returns list of list of integers representing the indexes of all the sublists in a N size list * @param n the size of the list * @return list of list of integers of indexes of the sublist */ public static List> allSubListIndexes(int n) { List> res = new ArrayList<>(); int allMasks = (1 << n); for (int i = 1; i < allMasks; i++) { res.add(new ArrayList<>()); for (int j = 0; j < n; j++) if ((i & (1 << j)) > 0) res.get(i-1).add(j); } return res; } 

Answer 5

这个简单函数可用于创建由给定数组或列表的所有可能子集的数字生成的所有可能数字的列表。

 void SubsetNumbers(int[] arr){ int len=arr.length; List list=new ArrayList(); List list1=new ArrayList(); for(int n:arr){ if(list.size()!=0){ for(int a:list){ list1.add(a*10+n); } list1.add(n); list.addAll(list1); list1.clear(); }else{ list.add(n); } } System.out.println(list.toString()); }