コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

「Heapのアルゴリズム」の版間の差分

出典: フリー百科事典『ウィキペディア(Wikipedia)』
削除された内容 追加された内容
Goma1661 (会話 | 投稿記録)
混同「ヒープソート
Cewbot (会話 | 投稿記録)
m Bot作業依頼: sourceタグをsyntaxhighlightタグに置換 (Category:非推奨のsourceタグを使用しているページ) - log
10行目: 10行目:
異なる{{math|''n''}}要素の置換を考える。Heapはこれらの要素の各置換をそれぞれ1度だけ生成するために入れ替える要素のペアを選択する体系的方法を発見した。その方法を再帰的やりかたで説明しよう。まずカウンター{{math|''i''}}を0にセットする。そして以下のステップを{{math|''i''}}が{{math|''n''}}と等しくなるまで繰り返す。まず最後の要素と隣接する最初の{{math|''n''−1}}要素の置換{{math|(''n''−1)!}}個をアルゴリズムで生成する。これは最後の要素で終わる置換を全て生成する。次に{{math|''n''}}が奇数の場合最初の要素と最後の要素を入れ替え、{{math|''n''}}が偶数の場合は{{math|''i''}}番目の要素と最後の要素を入れ替える(最初のイテレーションでは{{math|''n''}}の偶奇で違いはない)。{{math|''i''}}に1を加算し、最初に戻る。各イテレーションでこのアルゴリズムは「最後」の位置に移動した要素で終わる全置換を生成する。以下の疑似コードは長さ{{math|''n''}}のデータ配列の全置換を出力する。
異なる{{math|''n''}}要素の置換を考える。Heapはこれらの要素の各置換をそれぞれ1度だけ生成するために入れ替える要素のペアを選択する体系的方法を発見した。その方法を再帰的やりかたで説明しよう。まずカウンター{{math|''i''}}を0にセットする。そして以下のステップを{{math|''i''}}が{{math|''n''}}と等しくなるまで繰り返す。まず最後の要素と隣接する最初の{{math|''n''−1}}要素の置換{{math|(''n''−1)!}}個をアルゴリズムで生成する。これは最後の要素で終わる置換を全て生成する。次に{{math|''n''}}が奇数の場合最初の要素と最後の要素を入れ替え、{{math|''n''}}が偶数の場合は{{math|''i''}}番目の要素と最後の要素を入れ替える(最初のイテレーションでは{{math|''n''}}の偶奇で違いはない)。{{math|''i''}}に1を加算し、最初に戻る。各イテレーションでこのアルゴリズムは「最後」の位置に移動した要素で終わる全置換を生成する。以下の疑似コードは長さ{{math|''n''}}のデータ配列の全置換を出力する。


<source lang="pascal">
<syntaxhighlight lang="pascal">
procedure generate(n : integer, A : array of any):
procedure generate(n : integer, A : array of any):
if n = 1 then
if n = 1 then
24行目: 24行目:
end for
end for
end if
end if
</syntaxhighlight>
</source>


このアルゴリズムは非再帰的に書くこともできる。<ref>{{cite web|url=http://www.cs.princeton.edu/~rs/talks/perms.pdf|title=a talk on Permutation Generation Algorithms|accessdate=2018-06-03|last=Sedgewick|first=Robert|publisher=}}</ref>
このアルゴリズムは非再帰的に書くこともできる。<ref>{{cite web|url=http://www.cs.princeton.edu/~rs/talks/perms.pdf|title=a talk on Permutation Generation Algorithms|accessdate=2018-06-03|last=Sedgewick|first=Robert|publisher=}}</ref>


<source lang="pascal">
<syntaxhighlight lang="pascal">
procedure generate(n : integer, A : array of any):
procedure generate(n : integer, A : array of any):
c : array of int
c : array of int
54行目: 54行目:
end if
end if
end while
end while
</syntaxhighlight>
</source>


== 関連項目 ==
== 関連項目 ==

2020年7月5日 (日) 23:10時点における版

HeapのアルゴリズムをA (琥珀色)、B (青色)、C (シアン)、D (ダークレッド)の4文字に使ってできる24の置換と23のスワップの図

Heapのアルゴリズムn個のオブジェクトの全ての置換を生成するアルゴリズムである。1963年にB. R. Heapによって提案された。[1]このアルゴリズムは移動を最小化する。つまり、各置換は前の置換から1ペアを交換するだけで生成され、他のn−2要素を操作する必要はない。1977年の置換生成アルゴリズムの論評で、Robert Sedgewickはこのアルゴリズムをコンピュータによる現時点で最も効率的な置換生成用アルゴリズムと結論づけた。[2]

Heapのアルゴリズムによって生成されたn個のオブジェクトの置換列はn+1個のオブジェクトの置換列の最初になっている。したがってHeapのアルゴリズムは無限置換列を生成する(オンライン整数列大辞典の数列 A280318)。

概要

異なるn要素の置換を考える。Heapはこれらの要素の各置換をそれぞれ1度だけ生成するために入れ替える要素のペアを選択する体系的方法を発見した。その方法を再帰的やりかたで説明しよう。まずカウンターiを0にセットする。そして以下のステップをinと等しくなるまで繰り返す。まず最後の要素と隣接する最初のn−1要素の置換(n−1)!個をアルゴリズムで生成する。これは最後の要素で終わる置換を全て生成する。次にnが奇数の場合最初の要素と最後の要素を入れ替え、nが偶数の場合はi番目の要素と最後の要素を入れ替える(最初のイテレーションではnの偶奇で違いはない)。iに1を加算し、最初に戻る。各イテレーションでこのアルゴリズムは「最後」の位置に移動した要素で終わる全置換を生成する。以下の疑似コードは長さnのデータ配列の全置換を出力する。

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

このアルゴリズムは非再帰的に書くこともできる。[3]

procedure generate(n : integer, A : array of any):
    c : array of int

    for i := 0; i < n; i += 1 do
        c[i] := 0
    end for

    output(A)
    
    i := 0;
    while i < n do
        if  c[i] < i then
            if i is even then
                swap(A[0], A[i])
            else
                swap(A[c[i]], A[i])
            end if
            output(A)
            c[i] += 1
            i := 0
        else
            c[i] := 0
            i += 1
        end if
    end while

関連項目

脚注

  1. ^ Heap, B. R. (1963). “Permutations by Interchanges”. The Computer Journal 6 (3): 293–4. doi:10.1093/comjnl/6.3.293. http://comjnl.oxfordjournals.org/content/6/3/293.full.pdf. 
  2. ^ Sedgewick, R. (1977). “Permutation Generation Methods”. ACM Computing Surveys 9 (2): 137–164. doi:10.1145/356689.356692. 
  3. ^ Sedgewick, Robert. “a talk on Permutation Generation Algorithms”. 2018年6月3日閲覧。