Haskell/Clojureでrepeated_combinationを実装してみる

前回やった Haskell/Clojureで数学パズル：コインの両替 - Programmer's Note の問題5は、書籍の解答例のひとつに、Rubyのrepeated_combination()を使った解があった。

こいつは任意の回数、配列の要素の組み合わせを出してくれる関数で、探せばClojure/Haskellにもあるだろうけど、ちょうどいい感じの題材なので実装してみる。

任意の大きさのリスト[a,b,c,d,...]を任意の回数n、各要素の組み合わせを出す。

使い方

repeat_combination [1 2 3] 2
; -> ((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3))

repeat_combination [1 2 3] 3
; -> ((1 1 1) (1 1 2) (1 1 3) (1 2 1) (1 2 2) (1 2 3) (1 3 1) (1 3 2) (1 3 3) (2 1 1) (2 1 2) (2 1 3) (2 2 1) (2 2 2) (2 2 3) (2 3 1) (2 3 2) (2 3 3) (3 1 1) (3 1 2) (3 1 3) (3 2 1) (3 2 2) (3 2 3) (3 3 1) (3 3 2) (3 3 3))

アルゴリズムは２通りあって、深さ優先か幅優先か。

いろいろやってみたけれど、下記の実装が一番シンプルでわかりやすいな。幅優先で処理するやり方。

Haskellの実装：

comb :: [[Int]] -> [[Int]] -> [[Int]]
comb xs ys = [ x ++ y | x <- xs, y <- ys]

comb_n_times :: [[Int]] -> Int -> [[Int]]
comb_n_times xs 1 = xs    
comb_n_times xs n = comb xs (comb_n_times xs (n-1))

repeat_combination :: [Int] -> Int -> [[Int]]
repeat_combination xs 1 = [xs]
repeat_combination xs n = let ys = [[x] | x <- xs] 
                          in comb_n_times ys n

やっていることは以下のような感じ。

入力データを変換してから
[a,b,c] => [[a],[b],[c]]

１回目
[[a],[b],[c]] x [[a],[b],[c]]
  => [a,a][a,b][a,c][b,a][b,b][b,c][c,a][c,b][c,c]

２回目は１回目の結果にたいして、
[[a],[b],[c]] x [[a,a][a,b][a,c][b,a][b,b][b,c][c,a][c,b][c,c]]
  => [a,a,a][a,a,b][a,a,c] ....

以上を繰り返す

コードとしては分かりやすいが、SICPでいうrecusive processになっているので、末尾最適化できない。 nが大きいとStack Overflowを起こす。とはいえ、この幅優先な方法は、iterative processな実装も可能ではある。

深さ優先

一方、深さ優先で組み合わせを作っていくやりかたもある。プロセスはこんな感じ。

[a,b,c] x [a,b,c] x [a,b,c]

 a -> a -> a  => [a,a,a]
        -> b  => [a,a,b]
        -> c  => [a,a,c]
   -> b -> a  => [a,b,a]
        -> b  => [a,b,b]
        -> c  => [a,b,c]
 ...

こっちの方はClojureの実装を載せる。

(defn repeat-combination [xs n]
  (letfn [(comb-depth [cnt res]
            (if (zero? cnt)
              [res]
              (apply concat
                     (for [x xs]
                       (comb-depth (dec cnt)
                                   (conj res x))))))
          ]
    (if (= n 1)
      [xs]
      (comb-depth n []))))

こっちの方法はあまりメリットはないかな・・・。 iterative processな実装にすることができない（たぶん）。