打印列表的所有可能子集

小编典典

打印列表的所有可能子集

algorithm

我有一个元素列表（1、2、3），我需要获取该列表的超集（powerset）（不重复元素）。因此，基本上我需要创建一个类似于以下内容的列表列表：

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

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

阅读 280

2020-07-28

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

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

2020-07-28