全ての組み合わせ in Clean 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 - Clean

ブランクありで適当なのでコードがダサいかも。
簡単なので大丈夫なはずだが。

module crossproduct
import StdEnv
($) infixr 1;($) a b :== a b;(>>=) infixl 0;(>>=) a b = \ w -> (\ (x, w) -> b x w ) (a w);liftM m :== \ lst -> \ w ->  (m lst, w);
join del [x:xs]= (toString x) +++ del +++ (join del xs);
join _ [] = "";
:: Elem= ElemChar Char | ElemStr String | ElemInt Int
class toElem a  where
    toElem :: a -> Elem
instance toElem Int where
    toElem a = ElemInt a
instance toElem Char where
    toElem a = ElemChar a
instance toElem String where
    toElem a = ElemStr a
instance toString Elem where
    toString (ElemInt a) = toString a
    toString (ElemStr a) = a
    toString (ElemChar a) = toString a
Start w =snd ((stdio >>= liftM ( fwrites str) >>= fclose) w)
    where str = join "\n" $ map (join ",") $ crossProduct [] elems2
          elems2 = [map toElem [0,1],map toElem ['ab'], map toElem ["Foo","Bar"]]
crossProduct :: [Elem] [[Elem]] -> [[Elem]]
crossProduct knil [[x:xs]:ys] = crossProduct [x:knil] ys ++ (crossProduct knil [xs:ys])
crossProduct knil [[]:ys] =  []
crossProduct knil [] =  [knil]

DouKaku?

全ての組み合わせ

Posted feedbacks - Clean

Index

Feed

Other

Link

Pathtraq