java - java中的高效排列算法

Question

我正在尝试编写一种方法来计算幂集的所有排列，其中顺序很重要。我相信这些被称为“安排”。我的意思是:

{a} -> {{a}, {}}
{a,b} -> {{a,b}, {b,a}, {a}, {b}, {}}
{a,b,c} -> {{a,b,c}, {a,c,b}, {b,a,c}, {b,c,a}, {c,a,b}, {c,b,a}, {a,b}, {a,c}, {b,a}, {b,c}, {c,a}, {c,b}, {a}, {b}, {c}, {}}

等我的印象是，给定一个集合 S，我应该生成 S 的幂集的每个子集的每个排列。所以首先生成幂集，然后将置换函数映射到每个集合。

问题是这非常复杂——类似于 O(∑n!/k!) 且 k=0..n。

我想知道是否有任何现有算法可以非常有效地执行此类操作(可能是并行实现)。或者即使存在并行幂集算法和并行置换算法，我也可以将两者结合起来。

想法？

Answer 1

google 提供的 guava 库包含不同的方法来排列集合。

参见类 com.google.common.collect.Collections2 的 javadoc here .