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) であることは簡単に証明できます。

ヒープのアルゴリズムが (詳細で) いかにトリッキーであるかを示すのは、余分なスワップを 1 つ行うため、表現がわずかに間違っていることです。n が偶数の場合、追加のスワップはノーオペレーションですが、n が奇数の場合、生成される順列の順序が大幅に変更されます。どちらの場合でも、不要な作業を行います。正しいアルゴリズムについてはhttps://en.wikipedia.org/wiki/Heap%27s_algorithmを参照するか (少なくとも、今日は正しい)、Heap's algorithm permutation generatorでの議論を参照してください。

ヒープのアルゴリズムがどのように機能するかを確認するには、偶数の場合と奇数の場合の両方で、ループの完全な反復がベクトルに対して行うことを確認する必要があります。偶数長のベクトルを指定すると、ヒープのアルゴリズムを完全に繰り返すと、規則に従って要素が再配置されます

[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 に答える