Печать всех возможных подмножеств списка

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

Эта простая функция может использоваться для создания списка всех возможных чисел, сгенерированных цифрами всех возможных подмножеств данного массива или списка.

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

Answer 5

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