6

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

{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。

我想知道是否有任何现有的算法可以非常有效地完成这类事情（也许是并行实现）。或者即使存在并行幂集算法并且存在并行置换算法，我也可以将两者结合起来。

想法？

4

2 回答 2

1

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

请参阅此处的 com.google.common.collect.Collections2 类的 javadoc 。

于 2012-06-19T15:31:03.943 回答
0

为此，您首先生成 1-n 个槽的组合，其中 n 是幂集中元素的数量。例如，如果您有 3 个元素，那么您将拥有：

C( 3, 3 ) = 1 个组合 (abc)
C( 3, 2 ) = 3 个组合 (ab) (ac) (bc)
C( 3, 1 ) = 3 个组合 (a) (b) (c)

现在，您为每个组合生成排列。

有众所周知的算法来计算排列和组合。例如，Knuth 的“计算机编程的艺术”，第 4A 卷，第 7.2.1.2 和 7.2.1.3 节，准确地解释了如何构造相关算法。

于 2012-09-20T22:34:14.737 回答