Bir listenin olası tüm alt kümelerini yazdırma

Question

Öğelerim listesi (1, 2, 3) var ve bu listenin üst kümesi (powerset) (yinelenen öğeler olmadan) almam gerekiyor. Böylece temelde benziyor Listelerinin bir listesi oluşturmanız gerekir:

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

iyi nedir bu uygulamaya yol (bu durumda basitlik> verimliliği, liste çok büyük olmayacak)? Tercihen Java'da, ancak herhangi bir dilde bir çözüm yararlı olacaktır.

Answer 1

Kullanım bit maskesi:

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} 

Sen ikili ilk bit en sağdaki olduğunu biliyoruz:

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

İşte bütün değerleri bir bit maskesi vardır. Petar Minchev çözüme dayalı

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

bir java çözümü - cevaplar dize listesinde odaklı olduğunu fark ettim

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

. Sonuç olarak, daha genel bir cevabı paylaşmaya karar verdim. Umarım yararlı olur. (Soultion buldum başka çözümlere dayanmaktadır, ben genel algorithem bunu birleştirdi.)

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