全ての組み合わせ in OCaml DouKaku?

2個以上のリストlist1, list2, list3...が与えられたときに、その複数個のリストの中の要素を一つずつとりだして組にする方法の全通りのリストを返すコードを書いてください。

Pythonで表現すると下のようになります。

>>> c = CrossProduct([1,2,3,4], "abc")
>>> list(c.all())
[[1, 'a'], [1, 'b'], [1, 'c'], [2, 'a'],
 [2, 'b'], [2, 'c'], [3, 'a'], [3, 'b'],
 [3, 'c'], [4, 'a'], [4, 'b'], [4, 'c']]

>>> c = CrossProduct([0, 1], "ab", ["Foo", "Bar"])
>>> list(c.all())
[[0, 'a', 'Foo'], [0, 'a', 'Bar'], [0, 'b', 'Foo'], [0, 'b', 'Bar']
 [1, 'a', 'Foo'], [1, 'a', 'Bar'], [1, 'b', 'Foo'], [1, 'b', 'Bar']]

順番はこの通りでなくても構いません。返すものはリストと書きましたが、なんらかの「一度に全部をメモリ上に作成しないリスト状のモノ」がある言語ではそちらを使う方がおすすめです。数値や文字列を一つのリストに混在させるのがやっかいな言語では整数のリストに限定しても構いません。

このお題はZIGOROuさんとのやりとりにヒントを得て作りました。 (しまった、先にブログで公開されてしまった→Yet Another Hackadelic - 直積の導出と考えうる全ての値を網羅したハッシュの生成)

追記：サンプル出力が間違っていたのでoceanさんの解答を使って出力し直しました。

直積はcross productじゃなくてdirect productだったと思います。

#light
open List
let rec directProduct = function
    | [] -> [[]]
    | ls::lss -> [for l in ls for rest in (directProduct lss) -> l::rest]

多引数は困りますわっ。

module List = struct
  include List
  
  let rev_round2 f xl yl  =
    List.fold_left (fun accx x -> 
      List.fold_left (fun accy y -> f accy x y) accx yl
      ) [] xl;;
  
  let rev_round3 f xl yl zl =
    List.fold_left (fun accx x -> 
      List.fold_left (fun accy y -> 
        List.fold_left (fun accz z -> f accz x y z) accy zl
      ) accx yl
    ) [] xl;;
      
  let of_string str =
    let len = String.length str in
    let rec loop i accm =
      if i<0 then accm else 
      loop (pred i) ((*Char.escaped*) str.[i] :: accm);
    in loop (pred len) [];;
end;;

open List;;
let x_product2 = rev_round2 (fun accm x y -> (x,y)::accm);;
let x_product3 = rev_round3 (fun accm x y z -> (x,y,z)::accm);;

x_product2 [1;2;3;4] (of_string "abc");;
x_product3 [0;1] (of_string "ab") ["Foo";"Bar"];;

DouKaku?

全ての組み合わせ

Posted feedbacks - OCaml

Index

Feed

Other

Link

Pathtraq