打印列表的所有可能的子集

Question

我有一個元素列表（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<n;i++) 
     { 
      for(j=0;j<n-i;j++) 
      { 
       k=j+i; 
       for(int m=j;m<=k;m++) 
       { 
        s=s+m; 
       } 
       displaySubset(s); 
       s=""; 
      } 
     } 
    } 
    public static void displaySubset(String s) 
    { 
     String set=""; 
     for(int i=0;i<s.length();i++) 
     { 
      String m=""+s.charAt(i); 
      int num=Integer.parseInt(m); 
      if(i==s.length()-1) 
       set=set+list[num]; 
      else 
       set=set+list[num]+","; 
     } 
     set="{"+set+"}"; 
     System.out.println(set); 
    } 
    public static void main() 
    { 
     Scanner sc=new Scanner(System.in); 
     System.out.println("Input ur list"); 
     String slist=sc.nextLine(); 
     int len=slist.length(); 
     slist=slist.substring(1,len-1); 
     StringTokenizer st=new StringTokenizer(slist,","); 
     int n=st.countTokens(); 
     list=new String[n]; 
     for(int i=0;i<n;i++) 
     { 
      list[i]=st.nextToken(); 
     } 
     process(n); 
    } 
} 

Answer 3

根據斯托Minchev溶液中的Java解決方案 -

public static List<List<Integer>> getAllSubsets(List<Integer> input) { 
    int allMasks = 1 << input.size(); 
    List<List<Integer>> output = new ArrayList<List<Integer>>(); 
    for(int i=0;i<allMasks;i++) { 
     List<Integer> sub = new ArrayList<Integer>(); 
     for(int j=0;j<input.size();j++) { 
      if((i & (1 << 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 <T> 
* @return list of the different sublists that can be made from the list object 
*/ 
public static <T> List<List<T>>getAllSubLists(List<T>list) 
{ 
    List<T>subList; 
    List<List<T>>res = new ArrayList<>(); 
    List<List<Integer>> indexes = allSubListIndexes(list.size()); 
    for(List<Integer> 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<List<Integer>> allSubListIndexes(int n) { 
    List<List<Integer>> 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; 
}