打印列表的所有可能子集 [英] Printing all possible subsets of a list

问题描述

我有元素的列表（1，2，3），我需要得到该列表的超集（幂）（没有重复元素）。所以基本上我需要创建列表的列表，看起来像：

I have a List of elements (1, 2, 3), and I need to get the superset (powerset) of that list (without repeating elements). So basically I need to create a List of Lists that looks like:

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

什么是最好的（简单>效率在这种情况下，该列表将不巨大）的方式来实现这一点？ preferably在Java中，但在任何语言中的解决方案将是有益的。

What is the best (simplicity > efficiency in this case, the list won't be huge) way to implement this? Preferably in Java, but a solution in any language would be useful.

推荐答案

使用位掩码：

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}

您知道二进制的第一位是最右边。

You know in binary the first bit is the rightmost.

这篇关于打印列表的所有可能子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！