如何生成给定列表的幂集？

algorithm list java combinations

2022-09-01 14:39:04

我正在尝试生成给定长度N列表的所有2 ^ N - 1可能组合的集合。集合会将组合中的元素数映射到包含特定长度组合的组合的有序列表。例如，对于列表：

[A, B, C, D]

我想生成地图：

{
    1 -> [{A}, {B}, {C}, {D}]
    2 -> [{A, B}, {A, C}, {A, D}, {B, C}, {B, D}, {C, D}]
    3 -> [{A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}]
    4 -> [{A, B, C, D}]
}

生成的数据库应保持原始顺序（其中表示有序序列（），并表示无序组（）），并尽可能快地运行。[]List{}Set

我整天都在为一些递归代码而苦苦挣扎（我知道实现应该是递归的），但无法深入了解它。

是否有我可以使用的参考/此类算法的现成实现？

答案 1

你要找的基本上是功率集（也许减去空集）。番石榴实际上有一个方法：Sets.powerSet（）。您可以查看 Sets 类的源代码，以了解该方法是如何实现的，如果您想自己编写它;您可能需要修改它以返回 a 而不是 a，因为您希望保留顺序，尽管此更改不应太剧烈。一旦你有了电源集，迭代它并构建你想要的地图应该是微不足道的。ListSet

答案 2

你要问的是生成一个集合的所有可能的子集。您可以将其视为迭代大小为 N 的所有可能的二进制数组（列表的大小）：

000000...000
000000...001
000000...010
000000...011
etc.

为什么？答案很简单：1 表示子集中存在元素，而 0 表示元素不存在。

所以，基本算法是显而易见的：

s = [A, B, C, D]

for i=0 to 2^N-1:
   b = convert_number_to_bin_array(i)
   ss = calculate_subset_based_on_bin_array(s, b)
   print ss

在的位置迭代和并从中选择元素。calculate_subset_based_on_bin_arraybss[current]b[current] = 1

以上将打印出所有现有子集。您可以调整此算法，以便获得您在问题中要求的地图。