1

これは、辞書編集順列を注文するために私が見つけた段階的なプロセスです。

  1. 前に印刷された順列を取り、次の文字よりも小さい右端の文字を見つけます。この文字を「最初の文字」と呼びましょう。

  2. 「最初のキャラクター」の天井を見つけます。天井は、「最初の文字」よりも大きい「最初の文字」の右側にある最小の文字です。ceil 文字を「2 番目の文字」と呼びましょう。

  3. 上記の 2 つの手順で見つかった 2 つの文字を入れ替えます。

  4. 「最初の文字」の元のインデックスの後に部分文字列を (減少しない順序で) 並べ替えます。

ソース: http://www.geeksforgeeks.org/lexicographic-permutations-of-string/

私はすでに擬似コードを書いており、今からプログラミングを始めようとしています。アルゴリズムで何が起こっているかは理解していますが、なぜ機能するのかわかりません。ステップ 2 のように、天井の文字が「最初の文字よりも大きい、最初の文字の右側にある最小の文字」である必要があるのはなぜですか。このようにしないとうまくいかないことは理解していますが、そうするとうまくいく理由がわかりません。

アルゴリズムの各ステップが必要な理由を誰かが説明してくれれば、それは素晴らしいことであり、コードを開始するのがはるかに快適になります。

編集：最小の順列を見つけるために、部分文字列をacsending順序に再配置する理由を理解していることを言及する必要があります。私が理解していないのは、天井と最初の文字を交換する理由に関するステップ1と2です

4

4 に答える 4

2

順列に関する役立つリンク- アルゴリズムはそこで説明されています。

私もロジックを理解するのに苦労したので、ここに概要を説明します。

基本的に、順列する要素 (文字/数字..) のシーケンスは、接頭辞と接尾辞の 2 つのセクションに分けることができます。接尾辞は、「最初の文字」までのすべてです。

アルゴリズムは、「2 番目の文字」(サフィックスにあり、スワップされた要素の小さい方) を「最初の文字」(プレフィックスの右端の要素であり、大きい方) と交換することにより、プレフィックスを「増加」させます。 1）。「2 番目の文字」と「1 番目の文字」は、プレフィックスの増加が最小限になるように選択されます。

接頭辞で最小の増加 (スワップ操作で実行) を行うことで、シーケンスを増加 (最初の順列) から減少 (最後の順列) に変換すると、それらの要素の可能なシーケンスが「すべて」得られると言えます。

スワップ後にサフィックスがソートされるのはなぜですか? サフィックスを「できるだけ小さく」して、次の数回の繰り返しで「現在の」プレフィックスを増やす必要がないようにします（現在のプレフィックスとは、アルゴリズムのこのステップのプレフィックスを意味します）

于 2014-04-06T07:31:18.093 に答える
1

このアルゴリズムの主なアイデアは、与えられた順列の次の順列を見つける方法です。あなたが書いたリンクによると、最後に印刷された順列で右の文字よりも小さい右端の文字を見つけることで実行できます。

証拠：

P = P[1]p[2]p[3]..p[n] を最後に印刷された順列として示します。k が P[k] > P[k+1] のような右端の文字のインデックスであるとします。

Next の定義によれば、Next(P) = P[1]p[2]p[3]..p[k+1]p[k]p[k+2]p[k+3] です。 .p[n].

value(P) < value(P') < value(Next(P)) となる P' があるとします。

P[k'] != P'[k'] のような最小インデックスとして k' を示します。

3 つのオプションがあります。

  • k' < k: その場合、 value(P') > value(P) なので、 P'[k'] > P[k'] となります。しかし、インデックス k' までは Next(P) と P は同じなので、P'[k'] > Next(P)[k'] となり、k' までは同じです (k' < k) => value(P') < value(Next(P)) という事実とは対照的です。

  • k' > k: P'[k'] > P[k'] 値 (P') > 値 (P) であるため、k' P と P' が同じになるまで、k' が存在することがわかっています。 Next の定義とは対照的に (k が P[k] < P[k+1] の右端にあるという事実に対して)、P[k''] < P[k'] となるような ' > k'。これは、チェーン P[k']P[k'+1]..P[k''] で X < Y のような 2 つの隣接 X、Y を見つけることができるためです。

  • k' = k': Next(P)[k'] < P'[k] の場合、true ではない value(P') > value(Next(P)) が得られます。P'[k] = Next(P)[k] の場合、k は右端で、value(P') <= value(Next(P)) であるため、P' = Next(P) が得られます。 value(Next(P)) > value(P') であるため、true になります。また、P'[k] < Next(P[k]) の場合、オプション 2 と同様にはなりません。

したがって、そのような P' は不可能であることがわかります => Next(P) は、希望どおり P の次の順列です。

例: P = "DFEBCA" Next(P) = "DFECBA".

つまり、4 は P[i] < P[i+1] のような右端のインデックスであるため、k = 4 です。

他の順列 P' を見つけようとすると、 value(P) < value(P') < value(Next(P)) は見つかりません。

于 2013-07-19T12:52:22.513 に答える