我正在准备面试，试图记忆 Heap 算法：
procedure generate(n : integer, A : array of any):
if n = 1 then
output(A)
else
for i := 0; i < n; i += 1 do
generate(n - 1, A)
if n is even then
swap(A[i], A[n-1])
else
swap(A[0], A[n-1])
end if
end for
end if
这个算法是生成排列的一个著名算法。它简洁快速，并且与生成组合的代码配合使用。
问题在于：我不喜欢死记硬背，总是试图保留概念以“推导”算法。
这个算法真的不直观，我找不到一种方法来解释它如何工作。
请问有人可以告诉我为什么和如何在生成排列时使该算法按预期工作吗？
Heap算法可能不是任何合理面试题的答案。有一个更直观的算法可以按照字典序产生排列；虽然它的摊销时间是O(1)（每个排列），而不是O(1)，但在实践中并没有明显变慢，而且更容易推导。
字典序算法非常简单: 给定某些排列, 按照以下方式找到下一个排列:
步骤(1)和(3)都是最坏情况O(n)，但很容易证明它们的平均时间是O(1)。
Heap算法有多棘手（在细节上）可以通过你对其表达式的略微错误来体现，因为它执行了一次额外的交换操作;如果n是偶数，则这个额外的交换操作是无用的，但当n是奇数时，它会显着改变生成的排列顺序。在任一情况下，它都做了不必要的工作。请参阅https://en.wikipedia.org/wiki/Heap%27s_algorithm以获取正确算法（至少今天是正确的），或在Heap's algorithm permutation generator中查看讨论。
要了解Heap算法的工作原理，您需要查看循环的完整迭代在偶数和奇数情况下对向量进行的操作。给定一个长度为偶数的向量，Heap算法的一个完整迭代将按照规则重新排列元素。
[1,...n] → [(n-2),(n-1),2,3,...,(n-3),n,1]
而如果向量的长度为奇数，则仅交换第一个和最后一个元素：
[1,...n] → [n,2,3,4,...,(n-2),(n-1),1]
A[0] <-> A[n - 1]
A[1] <-> A[n - 1]
A[2] <-> A[n - 1]
...
A[n - 2] <-> A[n - 1]
A[0] <-> A[3]: DBCA
A[1] <-> A[3]: DACB
A[2] <-> A[3]: DABC
(IV) 这一系列步骤使得序列的顺序与之前完全相同：
Repeat n times:
Rotate the sub-sequence a[0...(n-2)] to the right
Swap: a[0] <-> a[n - 1]
直观上讲，这是正确的：
如果您有一个长度为5的序列，然后将其旋转5次，它最终保持不变。
在旋转之前取出0号元素，然后在旋转后将其与新的0号元素交换，不会改变结果（如果旋转n次）。
现在我们可以看到为什么(I)和(II)是正确的：
如果n为1： 很明显，在调用函数后，排序不会改变。
如果n为2： 递归调用“generate(n - 1, A)”不会改变排序（因为它调用第一个参数为1的generate）。 所以我们可以忽略那些调用。 在此调用中执行的交换导致右旋，参见(III)。
如果n为3： 递归调用“generate(n - 1, A)”导致右旋。 因此，此调用中的总步骤等于(IV) => 序列未改变。
重复n = 4、5、6、...的操作。
a[n]。如果你将其更改为交换 a[0] 和 a[n-1]，则会引入一个额外的交换，使排列序列不再是格雷码（这在未经校正的维基百科页面中很明显）。虽然它不是格雷码，但仍然可以通过所有排列序列，因此错误很容易被忽略。 - ricicbad 到 dbca，这不是一个格雷码，因为它不是两个元素的交换。 - ricin，（n-1），2，3，4，...，（n-2），1放置在最后一个位置，对于奇数长度的输入递归调用将元素n，（n-3），（n-4），（n-5），...，2，（n-2），（n-1），1放置在最后一个位置。因此，在任一情况下，所有元素都与n-1元素的所有排列相邻。function* permute<T>(array: T[], n = array.length): Generator<T[]> {
if (n > 1) {
for (let ix = 1; ix < n; ix += 1) {
for (let _arr of permute(array, n - 1)) yield _arr
let j = n % 2 ? 0 : ix - 1
;[array[j], array[n - 1]] = [array[n - 1], array[j]]
}
for (let _arr of permute(array, n - 1)) yield _arr
} else yield array
}
使用示例：
for (let arr of permute([1, 2, 3])) console.log(arr)
对我来说最难理解的部分是递归表达式，因为我还在学习它。
for i := 0; i < n; i += 1 do
generate(n - 1, A)
由于它递归地调用和返回每个 i，因此每当传回 n + 1 时可以实现最小更改。
只是一个小提示。堆算法将生成n！个组合。 例如，如果您将n = [1,2,3]作为输入传递，则结果将是n！，即