過去ログ
No．１１７４ 順列生成のアルゴリズム
[戻る] [ホームページ]No.15282 |
組合わせ方の列挙法について 投稿者---sanji(2004/07/06 15:13:03) |
||
1からnまでの整数の全組み合わせ方を出力する方法を考えています。 例えば１から３までなら 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1 の6通りの組合せを列挙することになります。 どのように考えれば良いか教えてください。 |
|||
| No.15286 |
Re:組合わせ方の列挙法について 投稿者---円零(2004/07/06 16:43:45) |
||
組み合わせではなくて順列ですね。 基本的には、手作業でやったときと同じ手順をなぞればできるんじゃないでしょうか。 つまり、 1) 1からnまでの数値を入れる要素数nの配列をnPn個用意する (仮に、int型の二次元配列Permとします。要素数はn! × nです)。 2) Perm[0][0]〜Perm[0][n - 1]に、1からnまでを順番に入れる。 3) Perm[x][n - 1]からPerm[x][0]へ向かって順番に見ていって（以後これを行とみなします）、 現在の値よりも大きい値が右側に含まれる最初の場所を見つける （"1,5,2,4,3"なら、"2"の位置。以下、Perm[x][y]とします。）。 4) その数値よりも大きくて、なおかつその中で最も小さい数値を、右側の数値の中から選ぶ （以下、vとします）。 5) Perm[x][0]〜Perm[x][y - 1]をPerm[x + 1][0]〜Perm[x + 1][y - 1]にコピーする。 6) Perm[x + 1][y] = v を代入する。 7) Perm[x + 1][y + 1]〜Perm[x + 1][n - 1]に、左側で使われていない値を小さい順に入れる （上の例では、"1,5,3,2,4"が次の行になる）。 8) 3)〜7)を、x = 0からn! - 1まで繰り返す（言うまでもありませんがこの"!"はC言語の演算子ではありません）。 |
|||
| No.15378 |
Re:組合わせ方の列挙法について 投稿者---sanji(2004/07/09 15:01:21) |
||
ありがとうございます。 やってみます！ やってみてまた分からないところが出たら、 また教えてください |
|||
| No.15396 |
Re:組合わせ方の列挙法について 投稿者---aki(2004/07/10 04:00:42) |
||
順列生成のアルゴリズムは結構たくさんあるようです。 http://f1.aaa.livedoor.jp/~pointc/log483.html http://www5.airnet.ne.jp/tomy/cpro/perm.htm http://www.sra.co.jp/people/miyata/algorithm/ |
|||