打印列表的所有可能子集

Question

我有一个元素列表 (1, 2, 3)，我需要获取该列表的幂集（超集）（不重复元素）。因此，基本上我需要创建一个看起来像这样的列表:

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

什么是最佳（在这种情况下，简单比效率更重要，列表不会很大）实现方法？最好用Java实现，但任何语言的解决方案都有帮助。

- Steve

---

你想要该列表的所有子集。我建议使用递归。但是，如果您正在处理超过30-40个元素的内容，您无法处理所拥有的巨大数据（超过1TB）。这用于什么？ - Per Alexandersson

你正在寻找的数据结构被称为幂集（与其他集合不同之处在于它还包含一个空集）。这个问题已经在SO上讨论过了。 - Mateusz Dymczyk

感谢Zenzen指引我正确的方向...我在https://dev59.com/xnI-5IYBdhLWcg3wy7wd找到了答案。 - Steve

那些不是排列，而是子集。 - job

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}

你知道在二进制中，第一个位是最右边的。

- Petar Minchev

---

这非常有趣...显然你比我聪明得多 - 给我一些时间来理解这个问题....N是原始列表中的元素数量吗？我是否将列表中的对象映射到整数？ - Steve

我认为这对于中等大小的列表或以上规模不起作用，allMasks整数将会溢出。 - mancini0

@PetarMinchev 我同意 :)，我的唯一使用情况是一个练习面试问题，我需要返回大小为50的列表的所有排列（2 ^ 50个排列，10 ^ 15个可能性），并且要满足一个谓词。我修改了你的解决方案以便使用大整数进行此操作。修改后的版本将在大约40年后产生正确答案，但至少面试官不能说这是一个不正确的解决方案。顺便说一下，你的解决方案很漂亮。 - mancini0

左移运算符如何计算可能子集的数量？即，当N=3时，'allMasks'如何知道有八个可能的子集？ - cluis92

@cluis92 - 查看所有长度为N的二进制数。对于N = 3，我们有0 0 0、0 0 1、0 1 0、0 1 1、1 0 0、1 0 1、1 1 0、1 1 1。实际上，1表示该位置上的数字参与子集。长度为N的二进制数的数量是2^N。左移运算符的行为如下：(1 << 0) = 1 = 十进制1，(1 << 1) = 10 = 十进制2，(1 << 2) = 100 = 十进制4，(1 << 3) = 1000 = 十进制8。这是二进制转十进制的直接结果。 - Petar Minchev

Answer 2

一份基于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;
}

- Nati Dykstein

Answer 3

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

- Shraddha Gupta

---

该程序很简单。首先，我们尝试获取所有可能的1-n位数字组合，直到每个1,2,3,...n位数字列表的最后一位数字为n。然后，对于每个组合，提取其每个字符（即数字），并显示存储在由此字符（数字）表示的单元索引中的子集元素。 - Shraddha Gupta

最好在答案中添加代码说明，而不是在评论中。仅包含代码的答案通常不被社区认为是好的答案，即使代码正确地回答了问题。 - рüффп

Answer 4

在给定的解决方案中，我们将遍历每个索引并包括当前和所有后续元素。

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

- Aman Thakur

Answer 5

我注意到答案都集中在字符串列表上。 因此，我决定分享更通用的答案。 希望它能够有所帮助。 （解决方案基于我发现的其他解决方案，我将其组合成了一个通用算法。）

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

- Itamar_laufer

Answer 6

这是一个简单的函数，可以用来创建一个列表，其中包含给定数组或列表的所有可能子集的数字生成的所有可能数字。

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

- Devashish

Answer 7

/*---USING JAVA COLLECTIONS---*/
/*---O(n^3) Time complexity, Simple---*/

int[] arr = new int[]{1,2,3,4,5};
//Convert the array to ArrayList
List<Integer> arrList = new ArrayList<>();
for(int i=0;i<arr.length;i++)
    arrList.add(arr[i]);
List<List<Integer>> twoD_List = new ArrayList<>();
int k=1; /*-- k is used for toIndex in sublist() method---*/
while(k != arr.length+1) /*--- arr.length + 1 = toIndex for the last element---*/
    {
       for(int j=0;j<=arr.length-k;j++)
       {
          twoD_List.add(arrList.subList(j, j+k));/*--- fromIndex(j) - toIndex(j+k)...notice that j varies till (arr.length - k), while k is constant for the whole loop...k gets incremented after all the operations in this for loop---*/
       }
       k++; /*--- increment k for extending sublist(basically concept the toIndex)---*/
   }
//printing all sublists
for(List<Integer> list : twoD_List) System.out.println(list);

- JIARUL HOQUE SARKER

Answer 8

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

- mancini0