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

ただ全ての組み合わせを得るだけなら、Gaucheだとライブラリ関数cartesian-productで
済んでしまいます：

gosh> (use util.combinations)
#<undef>
gosh> (write (cartesian-product '((1 2 3 4) (#\a #\b #\c) (a b c))))
((1 #\a a) (1 #\a b) (1 #\a c) (1 #\b a) (1 #\b b) (1 #\b c) (1 #\c a) (1 #\c b) (1 #\c c) (2 #\a a) (2 #\a b) (2 #\a c) (2 #\b a) (2 #\b b) (2 #\b c) (2 #\c a) (2 #\c b) (2 #\c c) (3 #\a a) (3 #\a b) (3 #\a c) (3 #\b a) (3 #\b b) (3 #\b c) (3 #\c a) (3 #\c b) (3 #\c c) (4 #\a a) (4 #\a b) (4 #\a c) (4 #\b a) (4 #\b b) (4 #\b c) (4 #\c a) (4 #\c b) (4 #\c c))#<undef>

これではつまらないので、ジェネレータにしてみました。
実行例：

gosh> (define z (cross-products-gen '((1 2) (3 4 5))))
z
gosh> (z)
(1 3)
gosh> (z)
(1 4)
gosh> (z)
(1 5)
gosh> (z)
(2 3)
gosh> (z)
(2 4)
gosh> (z)
(2 5)
gosh> (z)
#f

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

(use util.combinations)

(define (cross-products-gen lists)
  (let ((restart #f)
        (return #f))
    (lambda ()
      (let/cc k
        (set! return k)
        (cond (restart (restart #f))
              (else (cartesian-product-for-each
                     (lambda (p) (let/cc k (set! restart k) (return p)))
                     lists)
                    #f))))))

持ち上げました。

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

(use srfi-1)
(define (comprehension s fn) (append-map fn s))
(define (liftList2 p2)
  (lambda (S T)
    (comprehension S (lambda (s)
               (comprehension T (lambda (t)
                      (list (p2 s t))))))))
(define (product s t) (list s t))
(define directProduct (liftList2 product))

;;実行例
;;gosh> (directProduct (iota 2 1) (list 'h 'e))
;;((1 h) (1 e) (2 h) (2 e))