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さんの解答を使って出力し直しました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function cp(lists){
  if (size(lists) == 1){
    yield project(lists[0], {_x->{_x}})
  } else {
    for (r : cp(lists[1..])){
      for (m:r){
        for (a:project(lists[0], {e-> {e}+ m})) yield {a}
      }
    }
  }
}
function listcp(lists) list(project(cp(lists), {x->x[0]}))

println(listcp([[1,2,3,4], "abc"]))

すこし簡略化しました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

function cp(lists){
  if (size(lists) == 0){
    yield {}
  } else {
    for (lss : cp(lists[1..])){
      for (ls : lists[0]) yield {ls} + lss
    }
  }
}
printAll(cp([{1,2,3,4}, "abc"]))