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

Question

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

[A, B, C, D]

我要生成 map :

{
    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)，{}代表一个un有序组(Set))，并尽可能快地运行。

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

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

Answer 1

您要查找的基本上是 power set (减去也许是空集)。 Guava 实际上有一个方法:Sets.powerSet() .您可以查看source of the Sets class如果你想自己写，看看方法是如何实现的；您可能需要修改它以返回 List 而不是 Set 因为您想保留顺序，尽管此更改不应该太激烈。一旦你有了权力集，迭代它并构建你想要的 map 应该是微不足道的。