排列的堆算法

Question

我正在准备采访,我正在努力记住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

该算法非常着名,可以生成排列.它简洁快速,与代码密切配合,生成组合.

问题是:我不喜欢记住事情,我总是试图让概念在以后"推断"算法.

这个算法真的不直观,我找不到解释它如何对我自己起作用的方法.

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

Answer 1

Heap的算法可能不是任何合理的面试问题的答案.有一种更直观的算法可以按字典顺序产生排列; 虽然它是分摊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的算法是如何工作的,您需要查看循环的完整迭代对偶数和奇数情况的向量的作用.给定偶数长度的向量,Heap算法的完整迭代将使向量向左旋转一个位置.如果向量具有奇数长度,则在算法结束时,向量将被反转.您可以使用归纳证明这两个事实都是正确的,尽管这并不能说明为什么它是真的.查看Wikipedia页面上的图表可能会有所帮助.