堆的奇偶校验算法

Question

有人能解释一下为什么 Heap 的算法 使用条件语句检查 K 是偶数还是奇数并且交换不同在每一个？在网上找不到直观的解释

此代码来自Wikipedia

procedure generate(k : integer, A : array of any):
    if k = 1 then
        output(A)
    else
        // Generate permutations with kth unaltered
        // Initially k == length(A)
        generate(k - 1, A)

        // Generate permutations for kth swapped with each k-1 initial
        for i := 0; i < k-1; i += 1 do
            // Swap choice dependent on parity of k (even or odd)
            if k is even then
                swap(A[i], A[k-1]) // zero-indexed, the kth is at k-1
            else
                swap(A[0], A[k-1])
            end if
            generate(k - 1, A)

        end for
    end if

Answer 1

你不能真正解开你根据 k 的奇偶性改变交换行为的原因与 explanation/justification 为什么算法作为一个整体工作，这是一件复杂的事情演示，但基本上，它与 generate 对底层数组的不同副作用有关，具体取决于 k 是偶数还是奇数，并以交替方式利用这些副作用来探索整体排列space。这些副作用及其相互作用在数学上有点复杂，因此，为了简化讨论，首先我将算法重写为完全等效的形式，这样更容易推理。我们不是将对 generate 的第一次调用放在 for 循环之外并从 0 迭代到 k-1，而是将其放在内部，从 0 迭代到 k，并提前结束最后一次迭代（以避免在已生成当前 k 值的所有输出后进行不必要的交换。

procedure generate(k : integer, A : array of any):
  if k = 1:
    output(A)
  else:
    for i := 0; i < k; i += 1 do:
      generate(k - 1, A)
      if i + 1 = k:
        break
      if k is even:
        swap(A[i], A[k-1])
      else:
        swap(A[0], A[k-1])

但是，通过删除 break 语句让不必要的交换发生在最终循环迭代的尾端会产生相同的排列（尽管顺序不同），并使每次迭代的副作用程序更容易推理：

procedure generate(k : integer, A : array of any):
  if k = 1:
    output(A)
  else:
    for i := 0; i < k; i += 1 do:
      generate(k - 1, A)
      if k is even:
        swap(A[i], A[k-1])
      else:
        swap(A[0], A[k-1])

除此之外，这里是堆算法的基本思想（任何形式）：

使用给定的 k 值调用生成函数意味着置换数组的前 k 个元素（索引 k 及之后的所有元素都必须固定，因为没有交换涉及超过 [=21= 的索引]).为了排列这前 k 个元素，我们对 generate(k-1, A) 进行 k 次递归调用，并且在进行这些递归调用中的每一次之前，我们想要从我们正在排列到它的末尾的段（即进入第 k 个位置：索引 k-1），因为将不同的元素放在所有大小 k-1 排列的后面有效地生成所有大小 k 排列。我们从哪里交换以选择这个唯一元素的条件选择完全取决于调用 generate(k-1, A) 对基础数组的不同副作用，具体取决于 k-1 是偶数还是奇数，但重点是相同：在生成下一批大小为 k-1 的排列之前，选择我们尚未在 for 循环中使用的元素并将其交换回数组的第 k 个位置。

这些交换在此算法的修订版本中起作用的原因实际上非常简单。在 k-1 为偶数的情况下调用 generate(k-1, A) 的副作用是将数组的第一个 k-1 元素向右旋转一个位置，并使用奇数 [= 调用 generate(k-1, A) 21=] 实际上在元素顺序方面没有副作用：数组的第一个 k-1 元素最终恰好位于调用之前的位置。

举个偶数k的例子，如果我们在数组[1,2,3,4,5,...]上连续调用generate(4, A)，前4个元素就这样循环（后面的所有元素都是固定的） ):

[1,2,3,4,...]
[4,1,2,3,...]
[3,4,1,2,...]
[2,3,4,1,...]
[1,2,3,4,...]
...

如果我们在 [1,2,3,4,5,6,...] 上调用 generate(5, A)，数组顺序方面的副作用是空操作（前 5 个元素的所有排列仍然从递归调用中生成，只是当我们删除 break 语句时进行的额外交换抵消了排序的副作用）。

[1,2,3,4,5,6,...]
[1,2,3,4,5,6,...]
...

条件交换策略直接来自这些事实：

当 k 是偶数时，我们用奇数调用 generate(k-1, A)，它没有排序副作用，所以如果我们想在每次迭代中选择一个不同的元素交换到后面我们可以只使用 swap(A[i], A[k-1])，因为 i 每次迭代都会递增，而其他元素不会移动。

另一方面，当 k 为奇数时，我们用偶数调用 generate(k-1, A)，这会产生将元素向右旋转一步的副作用。这就是为什么我们只是重复地从 A[0] 中拉取：循环中对 generate 的偶数调用的副作用为我们完成了循环元素的工作：我们每次都可以从第一个位置抓取元素因为副作用会在每次迭代时将不同的元素放入该位置。

基本上，如果我们想在 for 循环中获取第一个 k 元素中的每一个并且它们是静态定位的，我们必须使用 i 的每个值，如果他们已经在骑自行车了，我们每次都必须从同一个位置抓取。它们是静态定位还是循环已经取决于 generate 基于 k 是偶数还是奇数的不同排序副作用。 even/odd k 的副作用的数学计算，这些副作用产生的循环，以及当您将 break 加回去时，这些特定规则起作用的原因背后的原因有所改变，但相同的规则仍然有效，你必须做的分析的一般形式来证明它也保持不变。

堆的奇偶校验算法

Heap's algorithm checking for odd and even

algorithm

logic

permutation

factorial

heaps-algorithm