21

我正在准备面试，我正在努力记住 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

这个算法是一个非常有名的生成排列的算法。它简洁而快速，并与代码一起生成组合。

问题是：我不喜欢背诵一些东西，我总是试图保留这些概念以便以后“推断”算法。

这个算法真的很不直观，我无法找到一种方法来向自己解释它是如何工作的。

有人可以告诉我在生成排列时该算法为何以及如何按预期工作？

4

3 回答 3

12

堆的算法可能不是任何合理面试问题的答案。有一种更直观的算法可以按字典顺序产生排列；虽然它是摊销 O(1)（每个排列）而不是 O(1)，但在实践中并没有明显变慢，而且动态推导要容易得多。

字典顺序算法描述起来非常简单。给定一些排列，通过以下方式找到下一个：

  1. 找到比其右边的元素小的最右边的元素。

  2. 将该元素与其右侧比它大的最小元素交换。

  3. 将排列的部分反转到该元素所在的右侧。

步骤 (1) 和 (3) 都是最坏情况 O(n)，但很容易证明这些步骤的平均时间是 O(1)。

Heap 的算法有多么棘手（在细节上）的一个迹象是，你对它的表达有点错误，因为它做了一次额外的交换；如果 n 为偶数，则额外的交换是无操作的，但会显着改变 n 为奇数时生成的排列顺序。无论哪种情况，它都会做不必要的工作。请参阅https://en.wikipedia.org/wiki/Heap%27s_algorithm了解正确的算法（至少今天是正确的）或查看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]

您可以使用归纳法证明这两个事实都是正确的，尽管这并不能提供任何关于为什么它是正确的直觉。查看维基百科页面上的图表可能会有所帮助。

于 2015-07-15T22:12:47.623 回答
2

我在这里找到了一篇文章试图解释它：为什么堆的算法有效？

但是，我认为它很难理解，所以想出了一个希望更容易理解的解释：

请暂时假设这些陈述是正确的（我稍后会展示）：

每次调用“生成”函数

(I)其中 n 为奇数，完成后将元素保持完全相同的顺序。

(II)其中 n 为偶数，向右旋转元素，例如 ABCD 变为 DABC。

所以在“for i”循环中

什么时候

  • n 是偶数

    递归调用“generate(n - 1, A)”不会改变顺序。

    因此 for 循环可以迭代地将 i=0..(n-1) 处的元素与 (n - 1) 处的元素交换，并且每次都会调用“generate(n - 1, A)”而另一个元素丢失.

  • n 是奇数

    递归调用“generate(n - 1, A)”将元素向右旋转。

    因此，索引 0 处的元素将始终自动成为不同的元素。

    只需在每次迭代中交换 0 和 (n-1) 处的元素即可生成一组唯一的元素。

最后，让我们看看为什么最初的陈述是正确的：

右旋

(III)这一系列的互换导致向右旋转一个位置：

A[0] <-> A[n - 1]
A[1] <-> A[n - 1]
A[2] <-> A[n - 1]
...
A[n - 2] <-> A[n - 1]

例如用序列 ABCD 试试：

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）。所以我们可以忽略这些电话。在此调用中执行的交换导致右转，请参见 (III)。

如果 n 为 3：递归调用“generate(n - 1, A)”导致右旋转。所以这个调用的总步数等于 (IV) => 序列不变。

重复 n = 4, 5, 6, ...

于 2017-05-09T14:42:33.957 回答
1

Heap 的算法构造所有排列的原因是它将每个元素与其余元素的每个排列相邻。当您执行堆算法时，对偶数长度输入的递归调用将元素n, (n-1), 2, 3, 4, ..., (n-2), 1放在最后一个位置，对奇数长度输入的递归调用将元素n, (n-3), (n-4), (n-5), ..., 2, (n-2), (n-1), 1放在最后一个位置。因此，在任何一种情况下，所有元素都与元素的所有排列相连n - 1。

如果您想要更详细的图形说明，请查看这篇文章。

于 2016-06-19T14:59:04.647 回答