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的powerset的每个子集的每个排列.所以首先生成powerset,然后将置换函数映射到每个集合上.

问题是这非常复杂 - 类似O(Σn!/ k!),k = 0..n.

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

思考？

Answer 1

谷歌提供的番石榴库包含不同的方法来排列集合。

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