アカウントを復元する際の反応と電光石火の速さについて、Habr政権に感謝します
だから、長い努力の成果...
辞書内の整数のすべてのパーティションを生成するための非再帰的アルゴリズム
すべての要素が降順で配置される順序は代替です。 で
インターネットは、組み合わせデータを生成するいくつかの方法を提示します
ただし、オブジェクトは、他の組み合わせアルゴリズムと同様に、
実装には、非再帰的と再帰的の2つのタイプがあります。 より一般的
オブジェクトの出力の順序を考慮しない、または実装しない実装
数の分割の原則に関する結論。
以下の実装は反対の原理で機能します。元の数は最初にユニットに分割され、アルゴリズムは配列のゼロインデックスの数が元の数の合計と等しくなるまで機能します。 このアルゴリズムの特徴は、理解するのが非常に簡単であるということですが、これはいくつかの詳細をそれから奪いません：
1）最初のオブジェクトは画面の最初に表示されるだけなので、ループから取り出され、実際に初期化されます。
2）ユニット転送を実装するにはいくつかの方法があります。これらの方法は、コードを単純化し、混乱を招く可能性があります。
3）この非再帰的な実装は、若干の変更を行った後、いくつかのプロセッサでの組み合わせオブジェクトの生成を説明する良い例として役立ちます。 世代をプロセッサに分離するには、a）番号で要素を決定し、初期化させるだけで十分です。 b）作業を停止する瞬間を決定します。 たとえば、1つのプロセッサで生成されたオブジェクトの数がわかっている場合、上位サイクルにもう1つ増分変数を導入し、必要な量に達した後に上位サイクルを終了する条件を変更するだけで十分です。
PHPコードは、アルゴリズムの正確さを示すためにのみ提供されており、冗長性の実装を追加する追加の言語ツールが含まれている場合があります。
アルゴリズムの説明
指定：ユニット形式の元の配列-A（1,1,1,1,1,1）。
手順
0）金額を受け取った場合（以下の実装の場合、ゼロインデックスが数値の合計に等しい場合）、アルゴリズムは停止します。
1）配列を左から右に移動し、配列Aで最初の最小要素-xを探します。
最後の要素は考慮されません（最小値の検索に参加しません）。
2）ユニットを最後（最後の要素）から見つかった最小要素xに移動する
（xを1つ増やし、最後の要素を1つ減らすことに相当します）。
4）変更された要素-x-の後のすべての要素の合計を単位に分解します。
例
A =（1,1,1,1,1）
2,1,1,1
2,2,1
3,1,1
PHPアルゴリズムコード
<?php /* . Generate all partitions.*/ $a = array( 1, 1, 1, 1, 1, 1, 1 ); $n = count($a); while (1) { /* . Print end exit.*/ print_r($a); if ($a[0] == $n) break; /* . First element of our dynamic array*/ $first_elem = $a[0]; /* . Length of an array*/ $c = count($a) - 1; $i = 0; while ($i != count($a) - 1) { /* . Here we search min. element.*/ if ($a[$i] < $first_elem) { $first_elem = $a[$i]; $min_elem = $i; } $i++; } if (empty($min_elem)) $min_elem = 0; /* "1". Here we transfer "1". */ $a[$min_elem]+= 1; $a[$c]-= 1; /* . We cut the array * and count the sum of elements.*/ array_splice($a, $min_elem + 1); $array_sum = array_sum($a); /* . Here we add 1 (fill) to the array ( taking into account the sum ).*/ for ($j = 0; $j != $n - $array_sum; $j++) $a[] = 1; /* . Unset min_elem.*/ unset($min_elem); } ?>
更新：
配列内の0を見つけて削除する操作は不要です（array_spliceを使用してから、配列の新しい塗りつぶしを使用するため）
結論
最後に1つの所見を共有したいと思います。なぜいくつかのアルゴリズムがすぐに明確で簡単にコーディングできるのか、他のアルゴリズムが私を苦しめているのかを理解するために非常に長い間努力しています... このアルゴリズムをほぼ即座にエンコードできたことに注意してください。ただし、各ステップの明確に理解できる説明を受け取った後でのみです。 そして、ここで重要なポイントがあります。アルゴリズムを理解し、説明することです-タスク同士のやり取りは簡単ではありません。 ただし、アルゴリズムの説明と記述のコンパイルでは、どの動詞がアルゴリズムのアクションを記述するかが特に重要です。これは、最終的には（主観的に）最終的な実装に影響を与える可能性があります。
文学
[1]ドナルドE.クヌース。 プログラミングの芸術。 巻 4.2008。
[2]デニス・リッチーとブライアン・カーニガン。 Cプログラミング言語。 1978。
[3]アレクサンドル・シェン。 アルゴリズムとプログラミング：問題と解決策。
[4] en.wikipedia.org/wiki/Number_Section
[5] en.wikipedia.org/wiki/De_Arte_Combinatoria
PS上記の参考文献リストにもかかわらず、アルゴリズムを再度推測する必要がありました。
別の追加：
このアプローチでサイクルから最初の要素を削除することは、パーティションの生成と組み合わせの生成の両方で有効です。 原則として、このアプローチは（実装では多少冗長ですが）他の組み合わせオブジェクトを生成するために非常に一般化されています。
更新
置換アルゴリズムと組み合わせたパーティションアルゴリズムを使用すると、すべての数の構成を生成できます。 考え方は簡単です。各パーティションに対して、このパーティションのすべての順列を生成する関数が呼び出されます。
組成物の生成。 Php
<?php /* . Generate all partitions.*/ $a = array( 1, 1, 1, 1, 1 ); $n = count($a); $h=0; while (1) { /* . Permutations and exit.*/ permute($a, $h); if ($a[0] == $n) break; /* . First element of our dynamic array*/ $first_elem = $a[0]; /* . Length of an array*/ $c = count($a) - 1; $i = 0; while ($i != count($a) - 1) { /* . Here we search min. element.*/ if ($a[$i] < $first_elem) { $first_elem = $a[$i]; $min_elem = $i; } $i++; } if (empty($min_elem)) $min_elem = 0; /* "1". Here we transfer "1". */ $a[$min_elem]+= 1; $a[$c]-= 1; /* . We cut the array * and count the sum of elements.*/ array_splice($a, $min_elem + 1); $array_sum = array_sum($a); /* . Here we add 1 (fill) to the array ( taking into account the sum ).*/ for ($j = 0; $j != $n - $array_sum; $j++) $a[] = 1; /* . Unset min_elem.*/ unset($min_elem); } /* . Permutations function.*/ function permute($b,&$h) { /* . * . * Here we make a copy and reverse our array. It is necessary to * stop the algorithm.*/ $a = $b; $b = array_reverse($b); while (1) { /* . Here we print and exit.*/ print_r($a); print "\n"; if ($a == $b) break; /* . * Here we search next permutation.*/ $i = 1; while ($a[$i] >= $a[$i - 1]) { $i++; } $j = 0; while ($a[$j] <= $a[$i]) { $j++; } /*. Here we change.*/ $c = $a[$j]; $a[$j] = $a[$i]; $a[$i] = $c; /* . Tail reverse.*/ $c = $a; $z = 0; for ($i-= 1; $i > - 1; $i--) $a[$z++] = $c[$i]; } } ?>