Drukowanie wszystkich możliwych podzbiorów listy

Question

Mam listę elementów (1, 2, 3) i potrzebuję uzyskać zestaw (zestaw) tej listy (bez powtarzania elementów). Więc w zasadzie muszę utworzyć listę list, który wygląda tak:

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

Jaki jest najlepszy (prostota> skuteczność w tym przypadku, ta lista nie będzie ogromny) drogę do wdrożenia tego? Najlepiej w Javie, ale przydatne byłoby rozwiązanie w dowolnym języku.

Answer 1

Stosować bitmasks:

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

Oto wszystkie bitmasks:

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} 

Wiesz binarnie pierwszy bit jest najbardziej na prawo.

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

Rozwiązanie oparte na Java Petar rozwiązania Minchev -

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

Zauważyłem, że odpowiedzi są skoncentrowane na liście String. W związku z tym postanowiłem udostępnić bardziej ogólną odpowiedź. Mam nadzieję, że będzie to pomocne. (Soultion opiera się na kolejnych rozwiązań znalazłem, że łączy go do ogólnej 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; 
}