1024個の箱からサンタクロースの汚れた靴下を見つけるための比較回数は7回


先日、チューリングの計算理論入門という本を読んでいたら、『サンタクロースの汚れた靴下』という話が書かれていました。

どういう話かというと、1024個のプレゼントの箱のうち、間違えて一つだけサンタクロースの汚れた靴下をいれてしまったのでその箱を探さなければいけないというもの。どうやらその汚れた靴下は他のプレゼントと比べて重いらしく、ちゃんとしたプレゼントは全て同じ重さらしい。なので、天秤が下がれば汚れた靴下が入っている箱がわかるということだ。

ただし、1個ずつ比較していくと最大512回かかってしまいます。そこで、ある子どもの妖精が1024個を2つに分けて512個ずつを天秤にかけたらいいとのこと。そしたら、重いほうのグループに汚れた靴下が入ってると分かるため、さらにそれを2つに分けて、256個の2つのグループに、それを繰り返して、128→64→32→16→8→4→2→1というグループで比較していけば、10回の比較で終わるとのことだ。

でもこれ、比較回数だけを考えれば、2等分ではなく、3等分にすればもう少し少ない比較回数で見つけることができます。

つまり、1024個を3等分して、a.341個、b.341個、c.342個のグループに分ける。この時、数が同じ341個のグループのaとbを比較して、aが重ければaに、bが重ければbに、吊り合っていればcに汚い靴下があるということが分かりります。ここで、cにあると分かったとして、さらにそれを3等分してd.114個、e.114個、f.114個として先ほどと同じ要領でdとeを比較、dにあると分かったとして、g.38個、h.38個、i.38個に分け、gとhを比較してgにあると分かったとして、j.12個、k.13個、l.13個に分け、同じ個数のkとlを比較し、kにあると分かったとしてm.4個、n.4個、o.5個にわけmとnを比較、oにあると分かったとしてp.2個、q.2個、r.1個に分け、pとqを比較。pにあるとわかればその2つを比較して重いほうに汚い靴下が入っているということが分かる。

というわけで汚い靴下が入っていたグループは342→114→38→13→5→2→1と減っていくので、最大でも7回の比較回数ですむことが分かる。

ただ、これは飽くまで比較回数の話であって、3等分するという点は少し効率が悪いかもしれませんね。後、もしもう少し比較回数が少なくなるような方法があれば教えて下さい。

for文の二重ループを一重ループにする方法


一重ループという言葉が正しいのかどうかはともかく、for文の二重ループをfor文一つだけにする方法についてメモとしてJavaScriptのコードで書きます。

プログラマのためのコードパズル ~JavaScriptで挑むコードゴルフとアルゴリズムを呼んで知った方法。といっても、方法は単純なので、やり方を知った今となってはなぜ今まで思いつかなかったんだろうとさえ思う。

2次元配列を探索する場合、たいていの場合は二重ループを使うことが多いと思います。例えば、九九を一の段から順番に探索していって、初めて50以上になった掛け算のみ出力するというプログラムを書こうと思った場合、二重ループを使うと下記のようになります(もっと実用性のあるプログラムを思いつけばよかったのですが、思いつきませんでした・・・。後、見つからなかった場合の判定もしていません)。

このように二重ループで書いた場合、全く同じbreak文の判定条件文を2回書かなければいけません。しかし、これを一重ループにすることにより、breakの判定条件文を1回だけですますことができます。例えば下記のような感じ。

for文の継続条件はiについて書いているのにたいし、for文の中のカウンタ変数の更新はjのみについて書いています。そうして、iについてはj+1が9未満にならない(つまり9以上)になる時にカウントするようにし、その時jは次のループで0になるように-1に変更します。これでループ一つだけで、2次元配列を探索し、breakの条件判定文も一つだけですむようになりました。

一見、何をしてるのか分かりにくいんですけどね。ただたんにbreakの判定条件を一つだけにしたいなら、関数化するほうが分かりやすいかもしれません。

2016/10/16追記:
二重ループを抜けるのには、ラベル構文というものを使ったほうがいいかもしれません(JavaScriptで多重ループを抜けるラベル構文について | while(isプログラマ))。

配列から重複なくランダムに複数の値を得る方法


カテゴリーはJavaScriptでコードもJavaScriptですが、どちらかというとアルゴリズム寄りの話です。たいがいのプログラミング言語では同様の方法で実装できる方法だと思います。

配列からランダムに複数の値を得たいということがあると思うのですが、普通にランダム関数でランダムの値を取得して、その配列のインデックスの値を取得しても重複してしまいます。
例えば下記のようなソースコード。

上記のコードは、arrという名前の配列からランダムに値を5つ取得してrandArrという配列に格納していくというプログラムですが、コンソールの結果は下記のようになりました。

randArrの中の値は重複せずに入っていることもありますが、かなりの確率で重複してしまいます。

じゃあ、重複せずにランダムで複数の値を取得するにはどうすればいいか考えてみると、最初に配列をシャッフルしてシャッフルした後の最初の5つを取得すれば重複せずに取得できます。ただ、全体をシャッフルしなきゃいけないので無駄が多そうです。なお、余談ですが、ランダムシャッフルはFisher-Yates法がよさそうです(参考:svartalfheim.jp – 配列を少ない仕事量でシャッフルするFisher-Yates法)。

ところで、よくよく考えたら複数の値を取得する配列が変更可能であれば、ランダムに取得した値はなくして大丈夫なわけです。ということは、ランダムで得た値の箇所をランダム値の上限のインデックス(1回目は配列の最後の要素)で置き換え、次に取得するランダム値の範囲を1減らせばランダムで取得する範囲はすでに取得した値以外になるわけです。
例えば、下記のようなサンプルコード。

コンソールには下記のように表示されました。

元々の配列がかなり変更することになりますが、重複なく値を取得できています。ループ回数も取得したい値の数(上記の例では5)だけですみました。

上記はJavaScript以外のプログラミング言語のことも考えて実装したアルゴリズムです。実は、JavaScriptだと配列の指定の箇所を取り除くspliceというメソッドがあるので、それを使うと上記のプログラムは下記のように実装できます(参考:Array.splice – JavaScript | MDN)。

コンソールの結果は下記のようになりました。

こちらだと元々の値を取得する配列は要素が減るだけなので、スッキリしています。もし、ランダム値を取得する順番をとわないのであれば、ランダムに値を減らした元々の配列に入っている値をランダムに取得した値と考えることもできそうです(例えば、100個の値が入っている配列からランダムに90個取得する場合、ループは90回でなく10回でいい)。

2014/05/13 23:39追記:spliceメソッドの戻り値は配列なので、0番目の値を入れるように指定しました。