Tuesday, October 07, 2008

組み合わせを作るアルゴリズム

ちょっと家にいなければならない用があったので、例のごとくProject eulerであそんでいました。
いましがた気持ちよく一問解けたので今日はもうおしまい。

ところで集合の部分集合をすべてリストアップするにはどうすればよいでしょうか。
つまり要素がN個の集合{1,2,3,4,...,N}があるとして、この集合から要素数1からN個までの部分集合を全部書き出すのです。{1},...,{N},{1,2},{2,3},....,{N-1,N},{1,2,3},...,,,,...{1,....,N}てのを全部です。どうやるのがよいでしょうか。順列だの組み合わせだのってのは概念は簡単なのですが、あんがい面倒なものが多いですね。


今日やった問題、最初勘違いしていて、部分集合を作る問題かと思って、これを実装してしまってました。結局これは使わなかったのですが。いざやろうとすると迷いますね。

先日買った本(赤い方の本)で調べたのです。「辞書順」は意外に大変だよ、と書いてある、そうそう、それやったことある。大変だった。簡単な方法はbinary countingだよと書いてありました。部分集合の数は2^N個あるので、1から2^N-1までの数を生成する。その数を2進数で表して1の立った場所を{1,...,N}の位置から選んで部分集合の要素とするというもの。なかなかシンプルでよろしいですね。これなら実装も簡単です。

No comments: