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

再帰で。

def cross_product(List[] lists) {
  if(lists.size() == 0) {
    return [[]]
  } else {
    return cross_product_2(cross_product(*cdr(lists)), lists[0])
  }
}

def cross_product_2(xs,ys) {
  xs.inject([]) { xval, x ->
    ys.inject(xval) { yval ,y ->
      yval + [[y, *x]]
    }
  }
}

def cdr(xs) {
  if(xs.size() < 2) {
    return []
  } else {
    return xs[1..-1]
  }
}


println cross_product([1,2,3],[4,5],[6,7])

やはり再起処理で解くのがスタンダードでしょうか。

def crossProduct( params ){

    def result = []

    switch(params.size()){
    case 1:
        // 何もしない
        break;
    case 2:
        params[0].each{ item1 ->
            params[1].each{ item2 ->
                result << ([] + item1) + ([] + item2)
            }
        }
        break;
    default:
        result = crossProduct( [crossProduct(params[0..1])] + params[2..-1])
        break;
    }

    result
}


crossProduct([[1,2,3,4], ["a", "b", "c"], ["あ", "い"]]).each{
    println it
}
crossProduct([[1,2,3,4], "abc"]).each{
    println it
}

DouKaku?

全ての組み合わせ

Posted feedbacks - Groovy

Index

Feed

Other

Link

Pathtraq