Phillip Fuchs 教授有一个非常简洁的算法，可以使用纯迭代方法生成对象数组的排列（参见 quickperm.org）。基本上有 2 种变体，一种倒计时算法和一种计数（向上计数）算法。想法是相同的，只是初始化问题以及是否增加或减少“里程表”数字不同。
我已经研究了一段时间的算法，并且可以理解这个想法，除了一个特定的细节。在算法中，以及Fuchs教授对其算法的解释中，如果high index是偶数，low index设置为0；而如果高位指数为奇数，则低位指数设置为高位指数所指向的“里程表”位（原文使用j、i、p[]）：
lowIndex = (highIndex %2 == 0) ? 0 : odometerDigit[highIndex];
我只是很难理解这个逻辑。为什么 highIndex 为偶数或奇数确定 lowIndex 应为 0 或 odometerDigit 中的值？Fuchs 教授没有对此提供更详细的解释，但这就是算法的“魔力”症结所在。我真的很感激任何可以帮助我进一步理解这一点的见解。
既然你踩了 N = 5（！），我会尝试一下。
除了 Fuchs 对递归的 [引证需要] 态度之外，我认为解释正在发生的事情的一种方法是他修改了以下递归算法。我希望这对你来说不是魔法。
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
第一个优化是，在内部堆栈帧中，只需要将变量的值j存储在他调用的数组中p。我不会打扰那个。
第二个优化是他做了一个交换切除术。我们可以通过不与自身交换元素来稍微减少交换。
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，与以前的版本不同，在返回之前不会恢复lst。permute2不是递归permute1的，因为它用来做脏活。
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，它将一个元素向左旋转。现在我们可以编写，它调用并查找下一个元素以交换到放置它的位置，但我们不能编写整个s 塔。lstlstpermute2apermute2lst[n - 1]permute2permute
我们需要一个关于我们尚未存在的permute函数行为的归纳假设，我们可以用它来证明下一个。这是一种创造性的行为，也是计算机科学中许多“魔法”的来源。我要写的可能不是对我的想法的真实描述。
我们正在研究的算法类别有两个自然约束。首先，这些算法使交换次数最少。其次，它们是自相似的，并且在移动最后一个元素之前耗尽了前 N - 1 个元素的所有排列。这些约束一起强制将交换的元素之一存储在与 Fuchs 对应的位置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无所谓。）那我们就要开始了
0 1 2 # forced w.l.o.g.
1 0 2 # forced because 2 cannot be moved yet.
唯一有趣的选择出现在这里。我们可以完成
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.
另一个可能的延续是
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 的第一种可能性都反转了排列。我将尝试构建permute3reverses lst。让我们看看它在 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
好吧，那没有用。我们需要奇数次递归调用才能使子数组反转。这是第一个建议，也许我们需要i奇数和i偶数的不同行为。
就像permute2，对于 N = 4，这个假设的算法将元素向左旋转一个。该主题的变化似乎是死胡同。这里已经够晚了，我已经做了足够多的徒劳无功的实验，Fuchs 的算法对我来说也开始看起来很神奇。
permute2a毕竟让我写。回想一下，将一个元素向左permute2旋转。lst如果在补偿旋转的同时permute2a随着位置的增加进行交换，它会重复交换相同的位置（例如，因为不能保证可以访问其他位置）。j0
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，这对几乎等同于 Fuchs 的算法。这对我来说似乎仍然很神奇，但现在是我收工的时候了。明天吧。
事实上，permute2a它不仅可以处理左旋转，还可以处理任何固定排列permute2，即循环，即，当重复应用于其域中的单个元素时，一个排列会给出所有其他元素。鉴于这种permute2行为方式，效果permute2a是应用permute2的 (N - 1) 循环置换 N 次，除了它在循环之间交换元素进出位置 0，效果是每个元素沿循环移动N - 1次，没有效果。因此，无论是什么， permute2aon的效果都是交换位置 0 和 N - 1。lstpermute2
现在我们要做的就是论证permute2可以使用permute2a. 的行为permute2a对permute2. 此外，由于permute2a仅涉及子数组的第一个和最后一个元素，因此当前的实现permute2大部分都在那里。事实上，如果 N 是偶数，它就可以正常工作。
0123
...
2103
2130
...
3120
3021
...
2031
1032
...
3012
N 奇数的问题是同一个元素将被交换两次到最后一个位置。
01234
...
31204
31240
...
41230
41032
...
31042
32041
...
42031
12034 # oops
我们现在要做的就是证明新permute2循环它的元素（当 N 是偶数时）。我将使用一些群论，因为我看不到简单的基本证明。在循环符号中，排列是
(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).
不相交的周期通勤。
(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 是偶数，因此 n-2 次连续交换无效。
(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)是一个循环。
(0 n-2)(0 n-1 n-2 ... 1)(0 n-2).
这是一个共轭循环，这也是一个循环。
(0 n-3 n-4 ... 1 n-2 n-1).
这是最终版本。我声称它相当于 Fuchs 的算法以显式堆栈为模。
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)