2

有人可以解释为什么堆算法使用条件语句检查K是偶数还是奇数，并且每个交换都不同？我在网上找不到任何直观的解释

此代码来自维基百科

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
4

1 回答 1

2

您无法真正解开基于k' 的奇偶性更改交换行为的原因与算法作为一个整体起作用的解释/理由，这是一个复杂的事情要证明，但基本上，它与不同的方面有关-effectsgenerate对底层数组的影响取决于k是偶数还是奇数，并以交替方式利用这些副作用来探索整个排列空间。这些副作用及其相互作用在数学上有点复杂，因此，为了简化讨论，首先我将把算法重新编写成一个更容易推理的完全等效的形式。而不是把第一个电话放在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])

顺便说一句，这里是堆算法的基本思想（以任何形式）：

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

这些交换在这个算法的修正版本中起作用的原因实际上非常简单。generate(k-1, A)调用where k-1is even的副作用是k-1将数组的第一个元素向右旋转一个位置，而调用generate(k-1, A)withoddk-1实际上在元素顺序方面没有副作用：k-1数组的第一个元素恰好位于它们所在的位置在打电话之前。

举个偶数k情况的例子，如果我们generate(4, A)连续调用 array [1,2,3,4,5,...]，前 4 个元素会像这样循环（并且它们后面的所有内容都是固定的）：

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

如果我们调用generate(5, A)on [1,2,3,4,5,6,...]，则数组顺序方面的副作用是无操作（前 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为我们完成了循环元素的工作：我们每次都可以从第一个位置抓取元素，因为副作用将不同的元素放入每次迭代的那个位置。

基本上，如果我们想抓取循环中的每一个第一个k元素for并且它们是静态定位的，我们必须使用 的每个值i，如果它们已经在循环，我们必须每次都从同一个位置抓取。generate它们是静态定位还是循环已经取决于基于k是偶数还是奇数的不同排序副作用。偶数/奇数 k 的副作用的数学，这些副作用产生的循环，以及为什么这些特定规则起作用的原因在您添加break后面时会发生一些变化，但相同的规则仍然有效并且一般形式你必须做的分析来证明它也保持不变。

于 2021-11-12T13:53:34.800 回答