algorithm - 制作用于查找所有可能排列的算法

Question

我发现只需将最后一个元素与中间元素交换，然后将中间元素与第一个元素交换，然后重复此操作，直到找到所有排列，即可轻松找到 3 个元素的排列。我尝试在元素超过 3 个时应用它，但它不起作用(对于 n = 4，我只发现 12 个排列)，是否有可能使其起作用？我知道有一个由 Steinhaus - Johnson - Trotter 制作的算法这可能就是我在说的，但我找不到对他们算法的很好的解释。顺便说一句，我不需要排列算法的(伪)代码。

Answer 1

递归地想，如果你有一个n个元素的集合，那么要生成所有可能的排列，将n个元素中的每一个放在第一个位置，然后生成剩余元素的所有可能的排列并添加与第一个元素连接。

实现这个的一个简单方法是定义一个函数，它依次将第一个元素与集合中的每个元素(包括它自己)交换，然后递归地调用它自己来生成剩余元素的每个可能排列，并且然后在返回(回溯)后将元素交换回来。很难进入更多细节，因为你说过你不想要伪代码。

这假定没有重复元素。

工作示例:

Generate permutations of (1, 2, 3):

Put each element as the first element and then generate all permutations of remaining elements:

    0 + permutations of (1, 2)

       Put each element as the first element and then generate all permutations of remaining elements:

       0 + 1 + permutations of (2)

          Put each element as the first element and then generate all permutations of remaining elements:

             0 + 1 + 2

       0 + 2 + permutations of (1)

          Put each element as the first element and then generate all permutations of remaining elements:

             0 + 2 + 1

    1 + permutations of (0, 2)

       Put each element as the first element and then generate all permutations of remaining elements:

       1 + 0 + permutations of (2)

          Put each element as the first element and then generate all permutations of remaining elements:

             1 + 0 + 2

       1 + 2 + permutations of (0)

          Put each element as the first element and then generate all permutations of remaining elements:

             1 + 2 + 0

    2 + permutations of (0, 1)

       Put each element as the first element and then generate all permutations of remaining elements:

       2 + 0 + permutations of (1)

          Put each element as the first element and then generate all permutations of remaining elements:

             2 + 0 + 1

       2 + 1 + permutations of (0)

          Put each element as the first element and then generate all permutations of remaining elements:

             2 + 1 + 0