如何生成给定List的幂集？

Question

我正在尝试生成长度为N的给定List的所有2 ^ N-1种可能组合的集合.该集合将组合中的元素数量映射到包含特定长度组合的有序组合列表.例如,对于List:

[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)),并尽可能快地运行.

我整天都在努力处理一些递归代码(我知道实现应该是递归的)但是无法深入了解它.

有没有我可以使用的参考/这种算法的现成实现？

Answer 1

您正在寻找的基本上是功率集(减去可能是空集).番石榴实际上有一个方法:Sets.powerSet().如果您想自己编写该方法,可以查看该类的源代码Sets以了解该方法的实现方式; 您可能需要修改它以返回a List而不是a,Set因为您希望保留顺序,尽管此更改不应过于激烈.一旦你获得了权力集,迭代它并构建你想要的地图应该是微不足道的.

Answer 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_array在迭代b和s从选择的元素s[current]在那里b[current] = 1.

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