목록의 가능한 모든 하위 집합 인쇄

Question

나는 List of elements (1, 2, 3)를 가지고 있으며 그 목록의 superset (powerset)을 가져야한다. 그래서 기본적으로 내가 보이는 목록의 목록 작성해야합니다 :

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

최고의 무엇이를 구현하는 방법 (이 경우 단순> 효율이 목록은 거대한를하지 않습니다)? 가급적 자바에서는 가능하지만 모든 언어의 솔루션이 유용 할 것입니다.

Answer 1

사용 비트 마스크 :

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} 

당신은 바이너리의 첫 번째 비트가 오른쪽 알고 :

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(); 
} 

여기에 모든 비트 마스크입니다. 페 타르 Minchev 솔루션을 기반으로

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

자바 솔루션 - 답변이 문자열 목록에 집중되는 것을 내가 눈치 챘을

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