给定一组值，列出所有可能的排列组合

Question

我对比较不同技术/方法来生成给定集合的所有可能排列很感兴趣。

- Bober02

---

可能是重复的问题：算法生成列表的所有可能排列？ - Tacet

Answer 1

你可以在性能、特定分布和简单性之间进行选择。通过特定分布，我指的是你是否关心输出的某种特定顺序，例如词典顺序。

据我所知，最佳性能算法是斯坦豪斯算法。从乘法常数的角度来看，它是最优的，因为只需要一个恒定数量的处理器指令来生成一个排列（不包括打印输出所需的指令，这并不总是必要的）。

还有一种非常简单的算法，可以按字典顺序产生排列，你可能会自己重新发明它作为递归过程，其性能为O(n.log(n).log(n))，因此与通过任何其他方法生成列表并对其进行排序的性能大致相同。 编辑：以下是简单算法的伪代码：

void permute(Element[] permutationPrefix, Set rest)
{
    if (rest.IsEmpty) {
        // permutationPrefix is now a full permutation
        print(permutationPrefix);
    } else {
        foreach (element in rest) {
            permutationPrefix.Append(element);
            permute(permutationPrefix, rest.Minus(element))
            permutationPrefix.Length--;  // cut away the last item
        }
    }
}

最初使用空的permutationPrefix和rest保存完整集合进行调用；如果该集合是一个排序数据结构，则排列将按字典顺序输出。

请注意，我们在每个递归调用中都会复制并修改集合，这是整个算法中最昂贵的操作，可能与print方法一起。单个集合复制的成本与排列总数n的对数成比例；由于递归调用堆栈的深度也是对数级别的，因此得出O(n.log(n).log(n))的性能估计。

（这个算法也适合转换成一个表现良好的随机排列生成器。）

- Jirka Hanika

---

什么是字典序算法？还有其他用于比较的吗？顺便感谢您的评论。 - Bober02

Answer 2

这个问题已经被问过并得到了答案（事实上多次问过）：

用于生成列表所有可能排列的算法？

给定整数的排列

我个人认为Steinhaus算法在思考问题时有些过度：它的速度并不比最原始的实现快多少。

以下是最基本实现的类似Java的伪代码：

List<List<Element>> generateAllPermutations(List<Element> input)
{
    List<Element> output = new ArrayList<Element>();
    if (input.size() == 0)
        return output;
    for (Element first : input) {
        for (List<Element> sequence : generateAllPermutations(input - first))
            output.add(first + sequence);
    }
}

- Tim Cooper

---

我认为这是不正确的。你在递归步骤中尝试做的是：给定集合S，生成S-{a}的所有排列，然后将a添加到每个排列中。这是错误的，因为你应该将该元素输入到每个排列的每个位置。 - Bober02

@Bober02：我不明白你的意思。 “我应该将该元素输入到每个排列的每个位置？” 例如：{1,1,1,1,1} ..？那不是一个排列。 - Tim Cooper