14

整数のタプルの順列を繰り返す必要があります。順序は、各ステップで要素のペアを交換して生成する必要があります。

これを行うはずの Heap のアルゴリズムに関するウィキペディアの記事 ( http://en.wikipedia.org/wiki/Heap%27s_algorithm ) を見つけました。擬似コードは次のとおりです。

procedure generate(n : integer, A : array of any):
    if n = 1 then
        output(A)
    else
        for i := 1; i ≤ n; i += 1 do
            generate(n - 1, A)
            if n is odd then
                j ← 1
            else
                j ← i
            swap(A[j], A[n])

このためのジェネレーターをPythonで作成しようとしました：

def heap_perm(A):
    n = len(A)
    Alist = [el for el in A]
    for hp in _heap_perm_(n, Alist):
        yield hp


def _heap_perm_(n, A):
    if n == 1:
        yield A
    else:
        for i in range(1,n+1):
            for hp in _heap_perm_(n-1, A):
                yield hp
            if (n % 2) == 1:
                j = 1
            else:
                j = i
            swap = A[j-1]
            A[j-1] = A[n-1]
            A[n-1] = swap

これにより、次の順序で順列が生成されます ([0,1,2,3] の入力の場合)。

0,1,2,3
1,0,2,3
2,0,1,3
0,2,1,3
1,2,0,3
2,1,0,3
3,1,2,0

and so on

これは、1 ペアの交換ではない最後のステップまで問題ないようです。

私は何を間違っていますか？

4

3 に答える 3

35

ヒストリカルプロローグ

ヒープのアルゴリズムに関するウィキペディアの記事は、この回答が書かれた後に修正されましたが、ウィキペディアの変更履歴で質問と回答で参照されているバージョンを確認できます。

ウィキペディアの疑似コードを実装するつもりなら、コードに (アルゴリズム的に) 問題はありません。提示されたアルゴリズムを正常に実装しました。

ただし、提示されたアルゴリズムはヒープのアルゴリズムではなく、連続する順列が単一の交換の結果になることを保証するものではありません。ウィキペディアのページでわかるように、生成された順列間で複数のスワップが発生する場合があります。たとえば、次の行を参照してください

CBAD
DBCA

それらの間に3つのスワップがあります（スワップの1つはノーオペレーションです）。

これはまさにコードからの出力です。コードは提示されたアルゴリズムの正確な実装であるため、驚くことではありません。

ヒープのアルゴリズムの正しい実装とエラーの原因

興味深いことに、疑似コードは基本的に Sedgewick のトーク スライド (ウィキペディア ページの参照 3) から派生したものであり、直前のスライドの順列のリストには対応していません。私はいくつかの調査を行い、私の分析を疑い始めるのに十分な、この誤った疑似コードの多くのコピーを見つけました。

幸いなことに、Heap の短い論文 (Wikipedia ページの参照 1) も参照しましたが、これはかなり明確です。彼の言うことは: (強調を追加)

プログラムは同じ一般的な方法を使用します。つまり、n 個のオブジェクトに対して、最初の (n-1) 個のオブジェクトを並べ替え、次に n 番目のセルの内容を指定されたセルの内容と交換します。このメソッドでは、この指定されたセルは、n が奇数の場合は常に最初のセルになりますが、n が偶数の場合は、1 から(n-1)まで連続して番号が付けられます。

問題は、提示された再帰関数が戻る前に常にスワップを行うことです (N が 1 でない限り)。したがって、実際には、ヒープが指定する(n-1)ではなく、1 からnに連続してスワップします。その結果、(たとえば) 関数が N==3 で呼び出された場合、次の yield の前に、呼び出しの最後に 2 つのスワップが発生します。 i==N のループ。N==4 の場合、3 つのスワップが行われます。(ただし、これらの一部はノーオペレーションになります。)

最後のスワップは正しくありません。アルゴリズムは、再帰呼び出しの後ではなく、再帰呼び出し間でスワップを行う必要があります。とスワップするべきではありませんi==N。

したがって、これは機能するはずです：

def _heap_perm_(n, A):
    if n == 1: yield A
    else:
        for i in range(n-1):
            for hp in _heap_perm_(n-1, A): yield hp
            j = 0 if (n % 2) == 1 else i
            A[j],A[n-1] = A[n-1],A[j]
        for hp in _heap_perm_(n-1, A): yield hp

セジウィックのオリジナル論文

私は Sedgewick の 1977 年の論文のコピーを見つけました (悲しいことに、ウィキペディアによって提供されたリンクは有料です)。彼が提示したアルゴリズムが正しいことを発見して喜んでいました。ただし、ループ制御構造 (Donald Knuth の功績によるもの) を使用していますが、これは Python や C プログラマーにはなじみのないものと思われるかもしれません: ミッドループ テスト:

Algorithm 1:

  procedure permutations (N);
      begin c:=1;
          loop:
              if N>2 then permutations(N-1)
              endif;
          while c<N:
              # Sedgewick uses :=: as the swap operator
              # Also see note below
              if N odd then P[N]:=:P[1] else P[N]:=:P[c] endif;
              c:=c+l
          repeat
       end;

注:スワップ行は 141 ページから取られ、Sedgewick はアルゴリズム 1 (140 ページ) の元のバージョンをヒープのアルゴリズムに一致するように変更する方法を説明しています。その行を除いて、残りのアルゴリズムは変更されていません。いくつかのバリエーションが提示されます。

于 2015-03-14T02:58:33.623 に答える
-1

ヒープのアルゴリズムに関するウィキペディアの記事から、非再帰的な擬似コードを Python に解釈しました。

A = ['a', 'b', 'c', 'd', 'e', 'f', 'g'] #the initial list to permute
n = len(A) #length of A
print(A) # output the first permutation (i.e. the original list A itself)
number_of_permutations = 1 #a variable to count a number of permutations produced by the script
total = [] #a list contaning all generated permutations
t = tuple(A) #tuple containing each permutation
total.append(t) #adding each permutation to total
c = [0] * n #c is the list used to track swapping of positions in each iteration of the Heap`s alrorythm.
i = 0 #index of positions in A and c. Serves as a pointer for swapping of positions in A.

while i < n:
    if c[i] < i: # test whether ith position was swapped more than i - 1 times
        if i % 2 == 0: #swapping the poitions in A
            A[0], A[i] = A[i], A[0]
        else:
            A[c[i]], A[i] = A[i], A[c[i]]
        print(A) #output of each permutation
        t = tuple(A) #convert each permutations into unmutable object (tuple)
        total.append(t) # appending each permutation as tuple in the list of all generated permutations
        number_of_permutations += 1 #increment number of performed permutations
        c[i] += 1 # incrementing c[i] is used to indicate that ith position was swapped
        i = 0 #returns the pointer to the 0th position (imitates recursion)
    else:
        c[i] = 0 #when ith position in A was swapped i - 1 times c[i] resets to zero
        i += 1 #pointer moves to the next position

print('Number of permutations generated by the script = ', number_of_permutations)

#Examining the correctness of permutions. Total number of permutations should be n! and there should not be any repeates
def factorial(n):
    """ Factorial function"""
    result = 1
    for number in range(1, n + 1):
        result *= number
    return result

print('Theoretical number of permutations (calculated as n!) = ', factorial(n))

for seq in total: #testing repeates
    count = total.count(seq)
    if count > 1:
        x = False
    else:
        x = True
print('The script does not generates repeats' if x == True else 'The script generates repeats')

また、結果の正しさのテストも導入しました (繰り返しのないすべての順列の数は n! に等しくなければなりません)。そして、スクリプトはうまく機能しているようです。私はまだそれがどのように機能するかを完全には理解していません。しかし、私はそれについての私の理解に従って、コードにコメントを入れました。

于 2021-11-07T19:52:32.500 に答える
-4

リストの順列を取得する最も簡単な方法は、 itertools モジュールの permutations 関数です。したがって、アルゴリズムが拘束力を持たない場合は、次のようにします。

from itertools import permutations

a = [1,2,3,4]
for item in permutations(a):
    print item
于 2015-03-14T06:47:00.050 に答える