アルゴリズムの完全な説明とはどういう意味ですか、なぜこれが必要なのでしょうか？
アメリカを発見せずにはできません。完全なアルゴリズムとは、紙にペンを使って実行されるオブジェクトに対する一連のアクションです。 完全な説明は、自然言語で記述されたすべてのステップであり、おそらく追加の数学表記を使用していますが、補助的なものにすぎません。 したがって、完全な説明は式ではなく、擬似コードでもなく、さらにブロック図でもありません。 この明白な論文から、同じ非常に単純ですが重要なことが続きます-かなり単純なアルゴリズムの実装を理解することは、式の削減または簡潔さによって妨げられる可能性があります。 この点で、私はハーブウィルフの意見が本当に好きでした。「公式は実際にはアルゴリズムです」とイゴールパックがこの記事で転載しました。 おそらく、異なるアルゴリズムの形で同じアルゴリズムを提示し、これらの表現に対する独自の認識を観察することで、なぜ私たちがより良く理解するアルゴリズムと他のアルゴリズムが悪くなるのかを明らかにすることができます。
アルゴリズムが言語から言語へと純粋に機械的に書き換えられる頻度に何度か気付きました。 おそらく、これは各ステップを掘り下げる時間があまりなく、適切な言語で結果をすぐに取得する必要がある場合の商業開発に適していますが、教育目的ではこの方法はあまり適していません。
自分自身を観察して、他の誰かのコードを見て、アルゴリズムを理解しているように見える状況に気づきました。それが実装されている言語は知っていますが、すべてのステップが表示されません。 著者はアルゴリズムを考え出し、可能な限り最小化したため、他のプログラマーのステップバイステップの実装を事実上隠しました。他のプログラマーは実装ツールに多くの注意を払っていますが、すべての努力は、彼らが知っている言語にトランスコードするために必要なこれらのツールの類似物を見つけることを目的としています
したがって、アルゴリズムの実装と簡単な正式な説明は、暗号のように見える場合があり、著者だけがすぐに理解できます。 自然言語でのアルゴリズムの説明については、おそらく複雑さへの答えは著者の言語自体にある可能性があります。説明では、誰もが用語の知識と理解に依存し、操作に使用される音声ツールのセットと組み合わせを使用するため いくつかのアルゴリズムを研究し、ある言語から別の言語への翻訳を観察した結果、私が自分で作った結論は、式とアルゴリズムの認識は、人間の活動のまったく異なる領域からの開発を含む一連の非常に深刻な研究のトピックになる可能性があるということです。
完全なアルゴリズムの実装が必要ですか？！
もちろん、たとえば、完全な組み合わせアルゴリズムの実装は、短縮されたものよりも何倍も遅く動作し、混乱を招き、くなります。 私の意見では、このような段階的な実装は、ある言語から別の言語に機械的に書き換えられたコードではなく、将来的にすべての略語と華やかさを理解する方法として役立つことがあるすべてのステップを理解する必要がある場合、一種のリバースエンジニアリングの道具として機能しますより速く、より短い対応物で。
繰り返しのない組み合わせ アルゴリズムの表現の変更
紙に印刷したときに、多くの組み合わせアルゴリズムが非常に単純に見えることは秘密ではありません。 たとえば、繰り返しのない組み合わせ（または繰り返しのない組み合わせ-少なくとも1つの要素が異なる）を生成するアルゴリズムは、ほとんど直ぐに理解することなく、実際には直観的に推測できます。 確かに、シート上のk = 3でn = 5のすべての組み合わせを書き出すとき、同じミスを数回行い、数字の1つを無視して間違った結果を得ました。 これにより、あるステップから別のステップに移動するときに多数のチェックを使用して、最大の視覚化で、紙上のアルゴリズムのプレゼンテーションをより体系的に実行する必要があると考えるようになりました。そうでなければ、数分で実装できるものを数時間引き伸ばすことができますでも日。
さらに、私の実験は完全な組み合わせ検索アルゴリズムのプレゼンテーションです
簡単に言うと、組み合わせを生成するアルゴリズムは次のように定式化されます。「...現在の組み合わせで、まだ最大値に達していない右端の要素を見つけます。 その後、1ずつ増やし、後続のすべての要素に最小値を割り当てます。」
出所
説明も実装も私にはあまり明確ではないので、数字への不注意を補い、説明をより詳細にするために、物事を少し複雑にし、いくつかの追加手順を追加することにしました。
説明
入力では、配列A = 123456 （たとえば）、昇順で並べ替えられます。 N = 6 （配列内の文字数）; K = 3と仮定します。
ループに入る前に、入力配列を2つに分割することを提案します-BとC、Bは1要素（両端を含む）からK（両端を含む）までの値を格納し、Cには他のすべて、つまりB [123]とC [456]を格納します
1）外側のループで、Bの位置Kの要素、つまりB [K]を反復処理し、配列Cで1より大きい要素を検索して交換します。 画面への出力。
2）さらに、条件-B [K]がNに等しい場合-配列の最後の要素、Kの左側の要素の検索サイクルが開始され、配列Cが1だけ大きくなります。 インデックスが0に達し、そのような要素がない場合、アルゴリズムは終了します。
3）Cの要素が見つかった場合、そのインデックスが検索され、Cの要素がさらに1つ減り、Bの要素が1つ増えます。 次に、配列Bを2つに分割します（配列なしでも可能です。省略オプションを参照）。 現在のアイテムの前と後。 現在の要素の後のすべてが配列Cに転送されます。
配列Bは増加順にインデックスKに増加し、余分な要素は配列Cから削除されます。 ネストされたループは終了します。 操作が新たに繰り返されます。
このアルゴリズムを使用すると時間がかかりますが、追加の配列を保存すると、注意に関連するエラーが回避され、実装がより簡潔になります。 その結果、アルゴリズムをより多くのステップに分解した後、ほとんどすぐにエンコードすることができました。
ただし、実装が紙に書かれていないことを警告する必要がありますが、PHPなどの言語では、非常に混乱しているように見える場合があります。 しかし、それにもかかわらず、正式には、アルゴリズムは正しく機能します。
繰り返しのない組み合わせを生成するための完全な非再帰アルゴリズム。 Php
<?php $a=array(1,2,3,4,5); $k=3; $n=5; $c=array_splice($a, $k); $b=array_splice($a, 0, $k); $j=$k-1; print_r($b); while (1) { if (in_array($b[$j]+1, $c)) { $m=array_search($b[$j]+1,$c); if ($m!==false) $c[$m]-=1; $b[$j]=$b[$j]+1; print_r($b); } if ($b[$k-1]==$n) { $i=$k-1; while ($i >= 0) { if ($i == 0 && !in_array($b[$i]+1, $c)) { break 2; } if (in_array($b[$i]+1, $c)) { $m=array_search($b[$i]+1,$c); if ($m!==false) $c[$m]=$c[$m]-1; $b[$i]=$b[$i]+1; $f=array_splice($b, $i+1); $b=array_splice($b, 0, $i+1); $c=array_merge($c,$f); $g=$i; while ($g != $k-1) { $b[$g+1]=$b[$g]+1; $g++; } $c=array_diff($c,$b); print_r($b); break; } $i--; } } }
コメント付きの簡略版
<?php $a=array(1,2,3,4,5); $k=3; $n=5; $c=array_splice($a, $k); $b=array_splice($a, 0, $k); $j=$k-1; // function printt($b,$k) { $z=0; while ($z < $k) print $b[$z++].' '; print "\n"; } printt ($b,$k); while (1) { // K N $m=array_search($b[$j]+1,$c); if ($m!==false) { $c[$m]-=1; $b[$j]=$b[$j]+1; printt ($b,$k); } if ($b[$k-1]==$n) { $i=$k-1; // while ($i >= 0) { // if ($i == 0 && $b[$i] == $n-$k+1) break 2; // $m=array_search($b[$i]+1,$c); if ($m!==false) { $c[$m]=$c[$m]-1; $b[$i]=$b[$i]+1; $g=$i; // B while ($g != $k-1) { array_unshift ($c, $b[$g+1]); $b[$g+1]=$b[$g]+1; $g++; } // C $c=array_diff($c,$b); printt ($b,$k); break; } $i--; } } } ?>
ステップごとのコード操作 （フレーム間の間隔20秒）
追加中
興味深いことに、このアルゴリズムは、組み合わせを生成するためのアルゴリズムに非常に簡単に変更できます。
繰り返します。 これを行うには、配列CとBを異なる方法で設定するだけで十分です。重複する値を削除した後、各パスでNの要素をCに追加します。
繰り返しのある組み合わせを生成するための完全な非再帰的アルゴリズム。 Php
内容
<?php $k=3; $n=5; $c=array(2,3,4,5); $b=array(1,1,1); $j=$k-1; // function printt($b,$k) { $z=0; while ($z < $k) print $b[$z++].' '; print "\n"; } printt ($b,$k); while (1) { // K N if (array_search($b[$j]+1,$c)!==false ) { $b[$j]=$b[$j]+1; printt ($b,$k); } if ($b[$k-1]==$n) { $i=$k-1; // while ($i >= 0) { // if ( $i == 0 && $b[$i] == $n) break 2; // $m=array_search($b[$i]+1,$c); if ($m!==false) { $c[$m]=$c[$m]-1; $b[$i]=$b[$i]+1; $g=$i; // B while ($g != $k-1) { array_unshift ($c, $b[$g+1]); $b[$g+1]=$b[$i]; $g++; } // C $c=array_diff($c,$b); printt ($b,$k); array_unshift ($c, $n); break; } $i--; } } } ?>
追加。 06/05/2017
このアルゴリズムは、繰り返しのない、または繰り返しのあるプレースメントを生成するためにも使用できます。 繰り返しのあるすべてのプレースメントを生成するには、すべての組み合わせを生成し、各組み合わせに対してすべての順列を生成します。 このタスク用に変更された置換アルゴリズムは、前の記事から提供されています。
繰り返しのあるすべてのプレースメントを生成するアルゴリズム。 Php
<?php set_time_limit(0); // function perm($b) { $a=array_reverse($b); while (1) { print_r($a); print '<br/>'; if ($a ==$b) break; $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; $a=array_merge(array_reverse(array_slice($a, 0, $i)),array_slice($a, $i)); } } // // n $k=5; $n=5; // $c=array(1,2,3,4,5); // b , k $b=array(1,1,1,1,1); $j=$k-1; // function printt($b,$k) { // perm($b); } printt ($b,$k); while (1) { // K N if (array_search($b[$j]+1,$c)!==false ) { $b[$j]=$b[$j]+1; printt ($b,$k); } if ($b[$k-1]==$n) { $i=$k-1; // while ($i >= 0) { // if ( $i == 0 && $b[$i] == $n) break 2; // $m=array_search($b[$i]+1,$c); if ($m!==false) { $c[$m]=$c[$m]-1; $b[$i]=$b[$i]+1; $g=$i; // B while ($g != $k-1) { array_unshift ($c, $b[$g+1]); $b[$g+1]=$b[$i]; $g++; } // C $c=array_diff($c,$b); printt ($b,$k); array_unshift ($c, $n); break; } $i--; } } } ?>
歌詞の実用的な追加
この記事を書いた後、私は彼らに図書館に行きました。 「非数学のトランザクション」（第1巻）V.A. ヴィスゲンシュタインに関する章でそのような行を残したオスペンスキーは、「活動、活動、そして再び活動-これはヴィットゲンシュタインの信条です。 彼にとって、プロセスは結果よりも重要です。 「私は結果を発見しませんが、それが達成される方法を発見します。」 V.A.ウスペンスキー（Wittgenstein）。
ポスト台本
すぐにいくつかのエラーに気付かずに、組み合わせの生成に関する前回の記事を時期尚早に公開したため、急いでおaび申し上げます。 Rosettacode.orgで、異なる言語での非再帰的および再帰的組み合わせ生成アルゴリズムの実装が発見されました。 Lipskyの本からアルゴリズムの実装もあります。