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

Question

假设我有一个包含 n 个元素的列表，我知道有 n 个!订购这些元素的可能方式。生成此列表所有可能顺序的算法是什么？例如，我有列表 [a, b, c]。该算法将返回 [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b , 一个]].

我在这里阅读 http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

但维基百科向来不善于解释。我不太明白。

Answer 1

基本上，对于从左到右的每个项目，生成剩余项目的所有排列(并且每个都与当前元素相加)。这可以递归地完成(如果你喜欢痛苦的话，可以迭代地完成)直到到达最后一项，此时只有一个可能的顺序。

因此对于列表 [1,2,3,4]，生成所有以 1 开头的排列，然后生成所有以 2 开头的排列，然后是 3，然后是 4。

这有效地减少了从查找四项列表到三项列表的排列问题之一。减少到2个再1个item列表后，全部都找到了。
使用 3 个彩球显示过程排列的示例:
(来自 https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg - https://commons.wikimedia.org/wiki/File:Permutations_RGB.svg )