既然你踩N = 5（！），我就来捅这个。

Since you stepped N = 5 (!), I'll take a stab at this.

[来源请求]福克斯的关于递归的态度之外，我想一个办法来解释发生了什么事情是，他修补了下面的递归算法。我希望这个人是不是魔术给你。

Fuchs's [citation needed] attitudes about recursion aside, I think one way to explain what's going on is that he's tinkered with the following recursive algorithm. I hope this one isn't magic to you.

def permute0(lst, n):
    if n < 2:
        print(lst)
    else:
        for j in range(n - 1, -1, -1):  # j in [0, n) descending
            # generate permutations with lst[n - 1] fixed
            lst[j], lst[n - 1] = lst[n - 1], lst[j]  # swap
            permute0(lst, n - 1)
            lst[j], lst[n - 1] = lst[n - 1], lst[j]  # swap back

第一个优化的是，在室内堆栈帧，该变量的唯一值Ĵ需要存储，阵列中，他称 P 。我不会去理会那一个。

The first optimization is that, in the interior stack frames, only the value of the variable j needs be stored, in the array that he calls p. I'm not going to bother with that one.

第二个优化是他做交换，切除。我们可以通过不换用自己的元素减少交换了一点。

The second optimization is that he's done a swap-ectomy. We can reduce the swapping a little by not swapping an element with itself.

def permute1(lst, n):
    if n < 2:
        print(lst)
    else:
        permute1(lst, n - 1)
        for j in range(n - 2, -1, -1):
            lst[j], lst[n - 1] = lst[n - 1], lst[j]
            permute1(lst, n - 1)
            lst[j], lst[n - 1] = lst[n - 1], lst[j]

要减少交换的数量进一步，我们将必须聪明。 permute2 ，不像previous版本，不返回之前恢复 LST 。 permute2 不是递归的，因为它使用 permute1 做肮脏的工作。

To reduce the number of swaps further, we're going to have to be cleverer. permute2, unlike the previous versions, does not restore lst before returning. permute2 is not recursive because it uses permute1 to do the dirty work.

def permute2(lst, n):
    if n < 2:
        print(lst)
    else:
        permute1(lst, n - 1)
        for j in range(n - 2, -1, -1):
            lst[j], lst[n - 1] = lst[n - 1], lst[j]
            permute1(lst, n - 1)

这是什么 permute2 做 LST ？忽略调用 permute1 ，其中离开 LST 不变，转动 LST 一个元素到左侧。现在，我们可以写 permute2a ，要求 permute2 并寻找下一个元素交换到 LST [N - 1] ，其中 permute2 所说的那样，但我们不能写的全塔置换秒。

What does permute2 do to lst? Ignoring the calls to permute1, which leave lst unchanged, it rotates lst one element to the left. Now we could write permute2a, which calls permute2 and looks for the next element to swap into lst[n - 1] where permute2 put it, but we can't write a whole tower of permutes.

我们需要了解还未现存置换的功能，我们可以用它来证明下一个向上的行为的归纳假设。 这是一个创造性的行为，和很多神奇的计算机科学的来源。的，我要写什么可能不是我是怎么想的一个现实写照。

We need an inductive hypothesis about the behavior of our not-yet-extant permute function that we can use to prove the next one up. This is a creative act, and the source of a lot of "magic" in computer science. What I'm about to write is probably not a realistic depiction of how I think.

我们正在寻找在类的算法有两个自然的约束。首先，这些算法使交换的最小数量。其次，他们是自相似性和排气的前N所有排列 - 移动之前最后1个元素。一起，这些约束迫使元件中的一个交换到被存储在对应于富克斯的的i位置

The class of algorithms we're looking in has two natural constraints. First, these algorithms make the minimum number of swaps. Second, they're self-similar and exhaust all permutations on the first N - 1 elements before moving the last. Together, these constraints force one of the elements swapped to be stored in the location corresponding to Fuchs's i.

N = 0: there's only one permutation
N = 1: there's only one permutation
N = 2: the graph looks like 0 1 - 1 0
N = 3: the graph looks like

0 1 2   1 2 0   2 0 1
  |       |       |
   -------+-------     all bipartite connections
  |       |       |
0 2 1   2 1 0   1 0 2

在启动不失一般性0 1 2 。 （对 LST 最初的内容并不重要。）然后我们要开始

Start without loss of generality at 0 1 2. (The initial contents of lst do not matter.) Then we have to start

0 1 2  # forced w.l.o.g.
1 0 2  # forced because 2 cannot be moved yet.

唯一有趣的选择就出现在这里。我们可以完成

The only interesting choice arises here. We could finish

2 0 1  # chose 1
0 2 1  # forced because 1 cannot be moved yet
1 2 0  # forced because we must move element 1 and 0 1 2 is already visited
2 1 0  # forced because 0 cannot be moved yet.

另一个可能延续

The other possible continuation is

1 2 0  # chose 0
2 1 0  # forced because 0 cannot be moved yet
2 0 1  # forced because we must move element 0 and 0 1 2 is already visited
0 2 1  # forced because 1 cannot be moved yet.

在这一点上，我注意到，N = 2和第一种可能性为N = 3这两种反向排列。我要去尝试构建 permute3 的挫折 LST 。让我们来看看它可能会做的N = 4。

At this point, I notice that N = 2 and the first possibility for N = 3 both reverse the permutation. I'm going to try to construct permute3 that reverses lst. Let's see what it might do for N = 4.

0 1 2 3
...
2 1 0 3
3 1 0 2
...
0 1 3 2
0 2 3 1
...
3 2 0 1
3 2 1 0
...
1 2 3 0  # oops

好了，没有工作。我们需要的递归调用奇数离开扭转了子数组。这是第一个建议，也许我们需要不同的行为我奇数和我连。

如同 permute2 ，对于N = 4，这个假设的算法旋转要素之一左侧。在该主题的变化似乎是死角。这足以晚在这里，我已经做了足够的无果而终的实验，即福克斯的算法开始似乎不可思议我为好。

Like permute2, for N = 4, this hypothetical algorithm rotates the elements one to the left. Variations on that theme seem to be dead ends. It's late enough here, and I've done enough fruitless experimentation, that Fuchs's algorithm is starting to seem magical to me as well.

让我写 permute2a 毕竟。回想一下， permute2 旋转 LST 一个元素的左边。如果 permute2a 使得互换与位置Ĵ，同时补偿的旋转增加，其反复交换相同的位置（比如 0 ，因为没有其他的位置是保证访问）。

Let me write permute2a after all. Recall that permute2 rotates lst one element to the left. If permute2a makes swaps with position j increasing while compensating for the rotations, it swaps the same position repeatedly (say 0, since no other position is guaranteed to be accessible).

def permute2a(lst, n):
    if n < 2:
        print(lst)
    else:
        permute2(lst, n - 1)
        for j in range(n - 2, -1, -1):
            lst[0], lst[n - 1] = lst[n - 1], lst[0]
            permute2(lst, n - 1)

现在，一个令人惊喜的时刻，我意识到，如果 permute2 名为 permute2a 而不是 permute1 ，两人几乎将相当于福克斯的算法。 这似乎仍然神奇的给我，但现在是时候让我收工了。也许明天。击>

Now, an aha moment where I realize that, if permute2 called permute2a instead of permute1, the pair almost would be equivalent to Fuchs's algorithm. This still seems magical to me, but it's time for me to call it a day. Maybe tomorrow.

其实， permute2a 可以处理不只是一个向左旋转，而是从 permute2 任何固定的排列是一个周期，即，即，当反复在其领域中的单个元素应用置换，使所有其他元素。鉴于 permute2 的行为这种方式， permute2a 的效果是适用 permute2 的（N - 1）-cycle排列N次，除了它交换进出位置0在循环之间的元素，条件是每个元件被沿周期N动议的效果 - 1次，其具有无影响。 permute2a 在 LST 的影响，无论 permute2 中，因此，交换位置0和N - 1

In fact, permute2a can handle not just a left rotation but any fixed permutation from permute2 that is a cycle, i.e., that a permutation that, when applied repeatedly to a single element in its domain, gives every other element. Given that permute2 behaves this way, the effect of permute2a is to apply permute2's (N - 1)-cycle permutation N times, except it swaps elements in and out of position 0 in between cycles, with the effect that each element is moved along the cycle N - 1 times, which has no effect. The effect of permute2a on lst, regardless of permute2, is thus to swap positions 0 and N - 1.

现在我们所要做的就是认为 permute2 可以使用 permute2a 。我们的事实， permute2a 的行为是不敏感的 permute2 实施细则帮了不少忙。此外，由于 permute2a 触及子阵只有第一个和最后一个元素，目前实施 permute2 是大多数途中有。事实上，当n为偶数，它的工作原理是。

Now all we have to do is argue that permute2 can use permute2a. We're helped a lot by the fact that the behavior of permute2a is insensitive to the implementation details of permute2. Moreover, since permute2a touches only the first and last element of the subarray, the current implementation of permute2 is most of the way there. In fact, if N is even, it works as is.

0123
...
2103
2130
...
3120
3021
...
2031
1032
...
3012

用N奇数的问题是，在同一元件将被交换两次到最后位置。

The problem with N odd is that the same element will be swapped twice into last position.

01234
...
31204
31240
...
41230
41032
...
31042
32041
...
42031
12034  # oops

现在我们所要做的就是证明新 permute2 周期的元素（n为偶数）。我会用一个小群论，因为我不能看到一个简单的初等证明。在周期符号，置换为

All we have to do now is show that the new permute2 cycles its elements (when N is even). I'm going to use a little group theory because I can't see a simple elementary proof. In cycle notation, the permutation is

(0 n-2)(0 n-1)(0 n-2)(1 n-1)(0 n-2)...(0 n-2)(n-3 n-1)(0 n-2)(n-2 n-1)(0 n-2).

不相交周期上下班。

Disjoint cycles commute.

(0 n-2)(0 n-1)[(0 n-2)...n-2 times...(0 n-2)](1 n-1)...(n-3 n-1)(n-2 n-1)(0 n-2).

由于n为偶数，正连续2次掉期交易没有影响。

Since n is even, n-2 consecutive swaps has no effect.

(0 n-2)(0 n-1)(1 n-1)...(n-3 n-1)(n-2 n-1)(0 n-2).

顺序（0 N-1）（1 N-1）...（N-3 N-1）（N-2 N-1），正如我们以前观察到的，是一个循环。

The sequence (0 n-1)(1 n-1)...(n-3 n-1)(n-2 n-1), as we observed before, is a cycle.

(0 n-2)(0 n-1 n-2 ... 1)(0 n-2).

这是一个共轭的周期，这也是一个循环

This is a conjugated cycle, which is also a cycle.

(0 n-3 n-4 ... 1 n-2 n-1).

下面是最终版本。我坚持认为这是相当于福克斯的算法模明确的堆栈。

Here's the final version. I claim that it's equivalent to Fuchs's algorithm modulo the explicit stack.

def permute3(lst, n):
    if n < 2:
        print(lst)
    else:
        permute3(lst, n - 1)
        for k in range(n - 2, -1, -1):
            i = n - 1
            j = 0 if i % 2 == 0 else k
            lst[j], lst[i] = lst[i], lst[j]
            permute3(lst, n - 1)