全ての組み合わせ in Common Lisp 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さんの解答を使って出力し直しました。

post comment

Posted feedbacks - Common Lisp

loop萌え～

(defun cross-product (&rest sequences)
  (labels ((rec (lists)
             (if (null (cdr lists))
                 (loop for a in (car lists) collect (list a))
                 (loop for x in (rec (cdr lists)) appending
                      (loop for a in (car lists) collect
                           `(,a ,@x))))))
    (rec (loop for arg in sequences collect (concatenate 'list arg)))))

(cross-product '(1 2 3 4) "abc")           ; => ((1 #\a) (2 #\a) (3 #\a) (4 #\a) (1 #\b) (2 #\b) (3 #\b) (4 #\b) (1 #\c) (2 #\c) (3 #\c) (4 #\c))
(cross-product #(0 1) "ab" '("Foo" "Bar")) ; => ((0 #\a "Foo") (1 #\a "Foo") (0 #\b "Foo") (1 #\b "Foo") (0 #\a "Bar") (1 #\a "Bar") (0 #\b "Bar") (1 #\b "Bar"))

DouKaku?

全ての組み合わせ

Posted feedbacks - Common Lisp

Index

Feed

Other

Link

Pathtraq