リストのすべての可能なサブセットを印刷

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は私が見つけた他のソリューションに基づいており、私は、一般的なalgorithemにそれを組み合わせる。）

/** 
* 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; 
}