如何生成给定列表的幂集? [英] How to generate the power-set of a given List?

问题描述

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

I'm trying to generate a collection of all 2^N - 1 possible combinations of a given List of length N. The collection will map the number of elements in a combination to an ordered list of combinations containing combinations of the specific length. For instance, for the 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))，并应尽可能快地运行.

The generated database should maintain the original order (where [] represents an ordered series (List), and {} represents an un-ordered group (Set)), and run as fast as possible.

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

I was struggling with some recursive code all day (I know the implementation should be recursive) but couldn't get to the bottom of it.

有没有我可以使用的参考/已经可以实现这种算法?

Is there a reference I can use/a ready implementation of such algorithm?

推荐答案

您正在寻找的实际上是 幂集 (可能减去空集).番石榴实际上为此提供了一种方法: Sets类的来源，以了解如果您想自己编写该方法，该方法如何实现；您可能需要修改它以返回List而不是Set，因为您想保留顺序，尽管此更改应该不会太大.设置好电源后，对其进行迭代并构建所需的地图应该很简单.

What you're looking for is essentially the power set (minus perhaps the empty set). Guava actually has a method for this: Sets.powerSet(). You can view the source of the Sets class to see how the method is implemented if you want to write it yourself; you might need to modify it to return a List instead of a Set since you want to preserve order, although this change should not be too drastic. Once you have the power set, it should be trivial to iterate over it and construct the map you want.

这篇关于如何生成给定列表的幂集?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！