Ruby で順列の列挙を実装する

最近いろいろな人が次の本をやっているのを見かけるので、気になって読み進めてみています。

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

ほとんどの問題の解答例が Ruby で書かれているのが特徴で（たまに JS もある）、Ruby の機能やライブラリをうまく使うと簡潔に書けることがわかります。

数学パズル的な問題なので、よく順列を列挙する必要に迫られます。順列は、次のように要素列から要素を選んで並べるときの並べかたです。高校数学で場合の数を計算するときに散々やるやつですね。

[1, 2] から 2 個とる順列 → {[1, 2], [2, 1]} の 2 通り
[1, 2, 3] から 2 個とる順列 → {[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]} の 6 通り

プログラミングで順列を解くとき、場合の数は n 個から r 個とるときは n! / (n - r)! を計算すれば求められるので簡単です。一方、実際の列挙ですが、Ruby では Array#permutation という便利メソッドがあり、これを呼び出すだけで OK です。

[1, 2, 3].permutation { |p| puts p }
# [1, 2, 3]
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 1, 2]
# [3, 2, 1]

これはとても便利なのですが、Array#permutation のような順列の列挙アルゴリズムを自前で実装しようとするとどうなるっけ……と不安を感じてしまったので、調べつつ Ruby で再実装してみました。

このスクリプトを実行すると、次の出力を得ます。

[["a", "b", "c"], ["a", "c", "b"], ["b", "a", "c"], ["b", "c", "a"], ["c", "a", "b"], ["c", "b", "a"]]
[["a", "b"], ["a", "c"], ["a", "d"], ["b", "a"], ["b", "c"], ["b", "d"], ["c", "a"], ["c", "b"], ["c", "d"], ["d", "a"], ["d", "b"], ["d", "c"]]

1 行目が ['a', 'b', 'c'] から 3 個とる順列の列挙、2 行目が ['a', 'b', 'c', 'd'] から 2 個とる順列の列挙です。1 行目のほうは何個とるかの引数を省略しているので、渡している配列のサイズ分とるようにしています。

アルゴリズムは次のページを参考にしました。再帰を使って、樹形図の作成をシミュレートすればよいことがわかります。

• 順列の列挙

……こういう筋力的な部分をもっと強くしておきたい人生でした。