最初について
配列内の値を交換した後にすべての順列を生成するアルゴリズムでは、この配列の一部、つまり末尾をラップする必要があります。 最初の実装では、これには4つのかなり高価な手法が使用されます。これは次のように要約されます。a）配列を2つから2つの操作に分割し、b）結果の配列の1つを裏返します c）配列を1つに接着します。
これを、たとえばPHP言語で表現すると、次の構造が得られます。
$a=array_merge(array_reverse(array_slice($a, 0, $i)),array_slice($a, $i));
読者が参照してこの記事に精通している場合、このコード行は実際にはCコードで使用される操作の完全な類似物であることに気付いたでしょう。
ただし、操作が関数に分散されているため、非常に混乱しています。
PHPでのこの式は読むのも非常に困難です（haskellプログラマーには当てはまりません）が、1つの重要なプラスがあります-最適化に必要なアクションを理解することは明白です。 この行の短い瞑想的な熟考の後、1つの操作として概念化され始めます。そのために、より単純なアナログ、そして最も重要なこととしてより速いアナログを見つけることができます。 PHPについては、次のものを入手しました。
$c=$a; $z=0; for ($i-=1; $i > -1; $i--) $a[$z++]=$c[$i];
配列の別のコピーをアルゴリズムに導入し、比較的単純なサイクルで配列の一部を再定義する必要がありました。1つの変数zも追加されました。
このセクションについてコメントします。1）要素の交換後、配列CはAと等しくなります。 2）forループは、交換（i）が行われたインデックスからゼロインデックスになり、iが減少します。
逆に、変数zは増加し、配列Aの一部には配列Cの要素が割り当てられますが、順序は逆です。 したがって、目的の結果、つまり反転部分を持つ配列Aが得られます。 実装では、超えないように変数iから1が減算されます。
1）完全なアルゴリズムをコーディングする、すなわち すべての冗長な操作で、どのように考えられ、紙に表示されるか。 2）1行でのいくつかの異なる操作の検索および削減; 3）可能であれば、この行での操作のより単純な類似物の検索。
Cコードは非常にコンパクトであることが判明しました。
見る
#include <stdio.h> #include <string.h> int main() { char a[] = "4321"; char d[5]; int fact = 24; int i, j, z; int y=0; char c; while (y != fact) { printf("%s\n", a); i=1; while(a[i] > a[i-1]) { i++; } j=0; while(a[j] < a[i]) { j++; } c=a[j]; a[j]=a[i]; a[i]=c; strcpy(d, a); z=0; for (i-=1; i > -1; i--) a[z++]=d[i]; y++; } }
変数がnのすべての順列の数の階乗に達すると、4サイクルと終了条件が判明しました。 私はわざわざ配列の比較を捨てて、少し速度を上げました。
更新する
wataruがコメントで正しく指摘しているように、配列の一部の構造もより単純なものに置き換えることができます。その結果、メインライブラリのみを使用するCの4サイクルのコードがあります。
編集されたコード
#include <stdio.h> int main() { char a[] = "4321"; int fact = 24; int i, j; int y=0; char c; while (y != fact) { printf("%s\n", a); i=1; while(a[i] > a[i-1]) i++; j=0; while(a[j] < a[i])j++; c=a[j]; a[j]=a[i]; a[i]=c; i--; for (j = 0; j < i; i--, j++) { c = a[i]; a[i] = a[j]; a[j] = c; } y++; } }
速度について
以前、 このリンクで最初の実装を再帰アルゴリズムと比較しましたが、結果は次のとおりです。
再帰アルゴリズムは、n = 11のランタイムを生成しました。
実2m9.213s
ユーザー0m2.920s
sys 0m26.290s
n = 11に対して作成された最初の記事のアルゴリズム：
実2m15.510s
ユーザー0m19.750s
sys 0m34.300s
n = 11の現在のバージョン
実1分46.459秒
ユーザー0m3.130s
sys 0m24.000s