java - 打印列表的所有可能子集

Question

我有一个元素列表（1、2、3），我需要获取该列表的超集（幂集）（不重复元素）。所以基本上我需要创建一个列表列表，如下所示：

{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

基于 Petar 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

In the given solution we iterate over every index and include current and all further elements.

class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            if(nums == null || nums.length ==0){
                return ans;
            }
            Arrays.sort(nums);
            List<Integer> subset = new ArrayList<>();
            allSubset(nums, ans , subset , 0);
            return ans;
        }
        private void allSubset(int[] nums,List<List<Integer>> ans ,List<Integer> subset , int idx){
            ans.add(new ArrayList<>(subset));
            for(int i = idx; i < nums.length; i++){
                subset.add(nums[i]);
                allSubset(nums, ans , subset , i+1);
                subset.remove(subset.size() - 1);
            }
        }
        
}

Answer 5

Peter Minchev 的解决方案修改为通过 BigInteger 处理更大的列表

public static List<List<Integer>> getAllSubsets(List<Integer> input) {
    BigInteger allMasks = BigInteger.ONE.shiftLeft(input.size());
    List<List<Integer>> output = new ArrayList<>();
    for(BigInteger i=BigInteger.ZERO;allMasks.subtract(i).compareTo(BigInteger.ZERO)>0; i=i.add(BigInteger.ONE)) {
        List<Integer> subList = new ArrayList<Integer>();
        for(int j=0;j<input.size();j++) {
            if(i.and(BigInteger.valueOf(1<<j)).compareTo(BigInteger.ZERO) > 0) {
                subList.add(input.get(j));
            }
        }
        System.out.println(subList);
        output.add(subList);
    }
    return output;
}

Answer 6

我注意到答案集中在字符串列表上。因此，我决定分享更通用的答案。希望它会有所帮助。（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 7

这是一个简单的函数，可用于创建由给定数组或列表的所有可能子集的数字生成的所有可能数字的列表。

void SubsetNumbers(int[] arr){
    int len=arr.length;
    List<Integer> list=new ArrayList<Integer>();
    List<Integer> list1=new ArrayList<Integer>();
    for(int n:arr){
        if(list.size()!=0){
            for(int a:list){
                list1.add(a*10+n);
            }
            list1.add(n);
            list.addAll(list1);
            list1.clear();
        }else{
            list.add(n);
        }
    }
    System.out.println(list.toString());
}