総当り(順列)を解かせる1

 

1週間ほど、夏休みをとらせて頂きました。
毎度、管理人イガジーです。

コンピュータが得意なのは「繰り返し処理」つまり
「総当り」です。人間なら途中で嫌になる作業でも
コンピュータは黙々とこなしてくれます。

例えば、虫食い算などの穴埋め問題を解くには
総当りで条件に合うかどうかを調べればよい訳です。

総当り処理の演習には、順列を生成するプログラムを
作ってみるのが良いでしょう。
順列の生成とは、例えば3桁ならば
123、132、213、231、312、321 の6パターンを
生成することです。

左から順に a[0], a[1], a[2] の箱を用意して
a[0]に1〜3、a[1]にも1〜3、a[2]にも1〜3を入れて
同じ数字があったらダメ、次に進むようにします。

3桁固定ならば、for 文を3つ書いても解けますが
任意桁(無限にはできないので、90桁くらいまで)とすると
ちょっと工夫が必要になります。

各桁の処理は結局同じことをするので、ここで登場する
のが「再帰」です。再帰とは、自分自身を呼ぶことです。

管理人イガジー自身は、再帰はあまり好きではありません。
再帰を避けて、できるだけループで組みたい派なのですが
この順列生成プログラムは、再帰だと割と簡単に書けましたが
ループにするには、ちょっとハマりました(できなくはありません)。

課題の条件は以下のとおりとします。
・コンストラクタに int 配列 を渡す

・このint配列が各桁をあらわし、0以外の数値が入っていると
そこは固定値として値は変更しない。(0の箱だけを変更する)
例えば、3桁で、a[0]=0; a[1]=2; a[2]=0; とすると
123、321 の2パターンが生成される。

・入れる数値の最大値は設定可能とする(ただし設定するのは
配列数以上)。
例えば、2桁で、最大値を3とすると、
12、13、21、23、31、32 の6パターンが生成される

ぜひ、作ってみてください。
解答例は、明日(の予定)。

この記事へのコメントはこちら

メールアドレスは公開されませんのでご安心ください。
また、* が付いている欄は必須項目となりますので、必ずご記入をお願いします。

内容に問題なければ、下記の「コメント送信」ボタンを押してください。