配列からべき集合を求める割と綺麗な関数とそれに至るまで
💁♂本記事で掲載するコードについて
今回紹介するコードの他、RubyやHaskellによる、べき集合を求める関数の実装をいくつか含めたリポジトリーをigrep / powersetsに公開したので興味があればご覧ください。使用した各種言語処理系のバージョンもそちらに記載しています。興が乗ったので、すべての実装についてHaskell製の最も素朴なバージョンと同じ振る舞いをするか、QuickCheckでテストまでしています。
きっかけ
半ば風が吹けば桶屋が儲かる的な話なのですが、2年半程前、Yokohama.rbというRubyのコミュニティーでこちら👇の問題を解こうとしたのがきっかけでした:
詳細は割愛しますが、この問題の解法の一つとして、入力された数における有効なビット番号の配列 --- 例えば2進数で10100となる数であれば下位ビットから数えて3ビット目と5ビット目が1なので[3, 5] --- の、べき集合を求めることがキーとなるものがあります。それに気づいた私は、べき集合を求める方法をあれこれ調べました。
最初に見つけた方法 --- といっても、ググってStack OverflowからRubyに翻訳したのとあまり変わりありませんが --- は、次のような素朴な再帰によるものでした:
def powerset_rec xs
return [[]] if xs.empty?
x = xs.shift
ps = powerset_rec(xs)
ps.map {|p| [x] + p } + ps
end
しかし、上記のような関数を用いて件の問題を解こうとすると、大きな数（この場合有効なビット番号が多い数）を与えたところでスタックが溢れてエラーになってしまいました。問題の要件上、少しやり方を変えればこの関数を使って解くこともできたのですが、私はこの時再帰呼び出しを使わないでべき集合を求める方法が気になって気になって仕方がなくなってしまい、それ以降元の問題そっちのけでべき集合を求める方法を考えていました。
結論
そうして試行錯誤してたどり着いた、再帰呼び出しをしない、最も簡潔な（かつ恐らく効率もよい）、べき集合を求める関数はこちらです:
def powerset_reduce xs
xs.reduce([[]]) do |last_result, x|
last_result.map {|p| [x] + p } + last_result
end
end
そう、おなじみreduceを使いました！中で使用している配列に対するmapや+も含めて、似た機能の関数はRuby以外の多くの言語にありますし、よくあるforループに変換するのも比較的簡単なはずです。つまり、他のプログラミング言語に移植するのも、再帰でのバージョンと同じくらい簡単なところがこの方法のメリットです。
以下が上記二つの実行例です:
irb(main):002:0> powerset_rec [9, 0, 8]
=> [[9, 0, 8], [9, 0], [9, 8], [9], [0, 8], [0], [8], []]
irb(main):003:0> powerset_reduce [9, 0, 8]
=> [[8, 0, 9], [8, 0], [8, 9], [8], [0, 9], [0], [9], []]
結果となる配列の順番が冒頭のpowerset_recと異なりますが、べき集合なので本稿では特に考慮しないことにします。ちゃんと列挙できているみたいですね！
日本語で軽く探した限り、少なくともRubyでこれに相当する実装を紹介した記事は見つかりませんでした。唯一エッセンスが似ていたのが、こちらの記事にあったPerlによる実装です:
my @a = (1,2,3);
my @p = ([]);
for my $a(@a) {
@p = (@p, map {[@$_, $a]} @p);
}
forループをreduceに置き換えれば、そのまま先ほどのpowerset_reduceに翻訳できそうですね！
たどり着くまで
べき集合の計算を、各要素が「存在する場合」と「存在しない場合」で分岐する2分木をたどる計算と解釈して走査してみたり、自前でスタックを作ってアセンブリーで関数呼び出しする要領でできないか、と考えたり、いろいろ紆余曲折ありましたが、最終的な答えに至ったきっかけは下記のように、元々の再帰呼び出しを利用したバージョンにおける、引数や途中の再帰呼び出しの結果をprintデバッグで確認したときでした:
def powerset_rec xs
return [[]] if xs.empty?
x = xs.shift
p x
ps = powerset_rec(xs)
p ps
ps.map {|p| [x] + p } + ps
end
その実行例は次のとおり:
irb(main):002:0> powerset_rec [3, 7, 0]
3
7
0
[[]]
[[0], []]
[[7, 0], [7], [0], []]
=> [[3, 7, 0], [3, 7], [3, 0], [3], [7, 0], [7], [0], []]
デバッグコードによって出力された値をご覧ください。最初の3行で引数の配列[3, 7, 0]にある各要素を出力した後、後半の3行でそれぞれの再帰呼び出しにおける結果に対して、配列の各要素を追加したりしなかったりしている、という動きが読み取れるでしょうか？
def powerset_rec xs
return [[]] if xs.empty?
x = xs.shift
p x # この行までで各要素を一つずつ処理して
ps = powerset_rec(xs) # この行以降で再帰呼び出しの結果を処理する
p ps
ps.map {|p| [x] + p } + ps
end
つまり、powerset_recの処理は、配列が空になるまで要素を一つずつ取り出す段階と、取り出した要素と直前の再帰呼び出しの結果を結合する段階とで明確に二分されており、再帰呼び出しでないと書きづらいと言うほど複雑なことをしているわけではない、と読み取れます。よくある木構造に対する再帰処理のように、要素を一つ処理する毎に何か処理をしてはまた再帰呼び出しする、という動作ではないんですね。
ということは、下記のありふれたループでやるように、最後の要素を処理したときの結果を保存する変数last_resultを用意しつつ、要素を一つずつ処理してlast_resultを更新していく... という定石が通用しそうです:
last_result = 初期値
配列.each do |x|
last_result = last_resultとxを使って何か計算
end
--- そしてそう、それはreduceメソッドで容易に書けるパターンでもあります:
配列.reduce(初期値) do |last_result, x|
last_resultとxを使って何か計算
end
powerset_reduceにおいて初期値やlast_resultがどのような値になるかも、powerset_recの動作を参考に導くことができます。powerset_recは、前述のとおり配列が空になるまで要素を一つずつ取り出した後、再帰呼び出しします。このとき渡される引数xsは、前の行でxs.shiftした後のxs、つまり先頭の要素を一つ取り除いた状態のxsです。このことから、powerset_recが再帰呼び出しするのは、現在の要素xを取り除いた分だけ小さくなった配列に対するpowerset_recの結果であると分かります。そうしてxを繰り返し抜き出した結果、最終的にpowerset_recに渡る引数xsは空配列になります。そこまで達すると、powerset_recはreturn [[]] if xs.empty?の行で直ちに[[]]を返します。べき集合の定義のとおり、空の集合のべき集合は、空の集合一つだけの集合ですしね。
一方powerset_reduceでは、これと逆の順番で処理すればいいのです。reduceメソッドの仕様上、初期値は引数として空の配列を受け取った時の戻り値と同じ値になるのですから[[]]を使います:
配列.reduce([[]]) do |last_result, x|
last_resultとxを使って何か計算
end
last_resultとxを使って何か計算については、powerset_recが「先頭の要素を一つ取り除いた配列に対するpowerset_recの結果」、psに対して繰り返しps.map {|p| [x] + p } + psして最後に[[]]を足し合わせるのですから、powerset_reduceでは初期値[[]]から積み上げるようにして、前の結果last_resultでps.map {|p| [x] + p } + ps相当のことをすれば良いのです:
配列.reduce([[]]) do |last_result, x|
last_result.map {|p| [x] + p } + last_result
end
これであとは配列をpowerset_reduceの引数xsに変えれば、powerset_reduceのできあがりです！
Discussion