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

(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))))))

普通に再帰で。（二番目の例の答えが違うけど、これでいいんですよね？）

def cross_product(*a):
    stack = []
    def traverse(i):
        if i == len(a):
            yield stack[:]
        else:
            for x in a[i]:
                stack.append(x)
                for the_stack in traverse(i + 1):
                    yield the_stack
                stack.pop()
    return traverse(0)

def print_cross_product(*a):
    for b in cross_product(*a):
        print b
    print

def main():
    print_cross_product([1,2,3,4], "abc")
    print_cross_product([0, 1], "ab", ["Foo", "Bar"])

if __name__ == '__main__':
    main()

using System;
using System.Collections;
using System.Collections.Generic;
class Program
{
  static void Main()
  {
    int[] ii = { 0, 1 };
    string[] ss = { "Foo", "Bar" };
    List<List<object>> lst = CrossProduct(ii, "ab".ToCharArray(), ss);
    foreach (List<object> l in lst)
    {
      foreach (object o in l) Console.Write(o + ", ");
      Console.WriteLine();
    }
  }
  static List<List<object>> CrossProduct(params IList[] lsts)
  {
    int[] pos = new int[lsts.Length];
    List<List<object>> lst = new List<List<object>>();
    int n1 = lsts.Length - 1;
    while (true)
    {
      List<object> l = new List<object>();
      for (int i = 0; i < lsts.Length; i++)l.Add(lsts[i][pos[i]]);
      lst.Add(l);
      int k = n1;
      while (k >= 0 && pos[k] == lsts[k].Count - 1) pos[k--] = 0;
      if (k < 0) break;
      ++pos[k];
    }
    return lst;
  }
}

サンプル出力間違い2連続orz
すぐ直します…orz

結果は（見易さのために改行を足しましたが）こんな感じです。

scala> crossproduct(List(1,2,3), List(4,5,6))
res14: List[List[Int]] = 
  List(List(1, 4), List(1, 5), List(1, 6), 
       List(2, 4), List(2, 5), List(2, 6), 
       List(3, 4), List(3, 5), List(3, 6))

scala> crossproduct(List(1,2),List(4,5),List(6,7))
res15: List[List[Int]] = 
  List(List(1, 4, 6), List(1, 4, 7), List(1, 5, 6), List(1, 5, 7), 
       List(2, 4, 6), List(2, 4, 7), List(2, 5, 6), List(2, 5, 7))

def crossproduct[T](xss: List[T]*) = {
  var ps = List(List[T]())
  for (xs <- xss.reverse)
    ps = for (i <- xs; j <- ps) yield i::j
  ps
}

Squeak Smalltalk で。

| input results gen |
input := #((0 1) 'ab' (Foo Bar)).
results := OrderedCollection new.
gen := input reversed
    inject: [:arr | results add: arr]
    into: [:block :colln |
        [:arr | colln do: [:ea | block value: arr, {ea}]] fixTemps].
gen value: #().
^results asArray

"=> #((0 $a Foo) (0 $a Bar) (0 $b Foo) (0 $b Bar)
   (1 $a Foo) (1 $a Bar) (1 $b Foo) (1 $b Bar)) "

ずいぶんカバレッジ下がりました。
勝手にHaskellに対抗意識を燃やしています。

1
2
3

crossp([],[]).
crossp([X|Xs],[I|Is]):-member(I,X),crossp(Xs,Is).
:-findall(X,crossp([[1,2,3],[uno,due,tre],[un,doux,trois]],X),Xs),writeln(Xs).

芸がない。そのくせ型という制約がある。

1	crossProduct = sequence :: [[a]] -> [[a]]

直積はcross productじゃなくてdirect productだったと思います。

#light
open List
let rec directProduct = function
    | [] -> [[]]
    | ls::lss -> [for l in ls for rest in (directProduct lss) -> l::rest]

fiber でジェネレータにしました。

「(...)」 というのは可変長引数をあらわすオブジェクトです。でも、コレ使うのなんかクラッシュする。。。

あと、配列の分配がきれいにかけないです。

CrossProduct: class {
    - _list: [];

    initialize: method(...) {
        (...).each_ordered_arg {
            // ここのコメントを削除するとなぜかクラッシュする＾＾
            if (it is String) {
                _list.push_back(it.split("").to_a);
            } else {
                _list.push_back(it);
            }
        }
    }

    all: method fiber {
        (fun (acc, rest) {
            if (rest.empty()) {
                yield acc;
            } else {
                x, xs: rest[0], rest.slice(1, rest.length);
                x {
                    callee(acc ~ [it], xs);
                }
            }
        })([], _list);
    }
}

c: CrossProduct([0, 1], "ab", ["Foo", "Bar"]);
c.all {
    it.p;
}

ちょうど、一つ前のお題で任意の個数からなるBool値のタプルの
組み合わせを生成するのに、同じようなコードを書きました。

余談ですが「コード：」のテキストボックスのフォントが、等幅だとうれしいのですが。

def CP(*l):
  def f(l):
    return ([a] + x for a in l[0] for x in f(l[1:])) if len(l) > 1 else ([a] for a in l[0])
  return f(l)

print CP([1,2,3,4], "abc")
print CP([0, 1], "ab", ["Foo", "Bar"])

単純に再帰で

import java.util.*;

public class Sample {
    private static void comb(ArrayList<Object> ans, List[] lists, int count, 
                            List<List> result) {
        if (count >= lists.length) {
            result.add(ans);
            return;
        }
        for (Object ele : lists[count]) {
            ArrayList<Object> a = new ArrayList<Object>(ans);
            a.add(ele);
            comb(a, lists, count + 1, result);
        }
    }

    public static List combination(List... lists) {
        List<List> result = new ArrayList<List>();
        comb(new ArrayList<Object>(), lists, 0, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(combination(Arrays.asList(0, 1),
                                       Arrays.asList('a', 'b'),
                                       Arrays.asList("foo", "bar")));
    }
}

おっと、ジェネレータは単にprintしてもダメだった。

ちょっとだけ修正。

def CP(*l):
  def f(l):
    return ([a] + x for a in l[0] for x in f(l[1:])) if len(l) > 1 else ([a] for a in l[0])
  return f(l)

print list(CP([1,2,3,4], "abc"))
print list(CP([0, 1], "ab", ["Foo", "Bar"]))

ether さんの #2152 の簡潔さに感心しつつ、それをヒントにして同様のことを Squeak Smalltalk で。

| input |
input := #((0 1) 'ab' (foo bar)).
^input reversed inject: #(()) into: [:arrs :colln |
    colln inject: #() into: [:rs :elem | rs, (arrs collect: [:arr | {elem}, arr])]]

もう１つおまけ

static List<List<object>> CrossProduct(params IList[] lsts)
{
  List<List<object>> lst = new List<List<object>>();
  lst.Add(new List<object>());
  foreach (IList il in lsts)
  {
    List<List<object>> l = new List<List<object>>();
    foreach (List<object> ls0 in lst)
    {
      foreach (object o in il)
      {
        List<object> ls = new List<object>(ls0);
        ls.Add(o);
        l.Add(ls);
      }
    }
    lst = l;
  }
  return lst;
}

1行にしてみました。

def crossProduct(as:List[Any]*) = {
  as.reverse./:(List(List[Any]())){for(i <-_; j <-_) yield j::i}
}


println(crossProduct(List(1,2,3,4), List('a', 'b', 'c')))
println(crossProduct(List(0,1), List('a', 'b'), List("Foo", "Bar")))

引数の数(リストの数)を固定する

crossProduct2 = concatMap . (. repeat) . zip
crossProduct3 = (. crossProduct2) . (.) . crossProduct2
crossProduct4 = (. crossProduct3) . (.) . (.) . crossProduct2
crossProduct5 = (. crossProduct4) . (.) . (.) . (.) . crossProduct2
crossProduct6 = (. crossProduct5) . (.) . (.) . (.) . (.) . crossProduct2
crossProduct7 = (. crossProduct6) . (.) . (.) . (.) . (.) . (.) . crossProduct2

-- Test data

data RGB = Red | Green | Blue  deriving (Bounded,Enum, Show)
data ENWS = East | North | West | South deriving (Bounded,Enum, Show)

allItems :: (Bounded a, Enum a) => [a]
allItems = [minBound..maxBound]

test = crossProduct4 (allItems::[()]) (allItems::[Bool]) (allItems::[RGB]) (allItems::[ENWS])

{-
*Main> test
[((),(False,(Red,East)))
,((),(True,(Red,East)))
,((),(False,(Green,East)))
,((),(True,(Green,East)))
,((),(False,(Blue,East)))
,((),(True,(Blue,East)))
,((),(False,(Red,North)))
,((),(True,(Red,North)))
,((),(False,(Green,North)))
,((),(True,(Green,North)))
,((),(False,(Blue,North)))
,((),(True,(Blue,North)))
,((),(False,(Red,West)))
,((),(True,(Red,West)))
,((),(False,(Green,West)))
,((),(True,(Green,West)))
,((),(False,(Blue,West)))
,((),(True,(Blue,West)))
,((),(False,(Red,South)))
,((),(True,(Red,South)))
,((),(False,(Green,South)))
,((),(True,(Green,South)))
,((),(False,(Blue,South)))
,((),(True,(Blue,South)))]
-}

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"))

配列でお茶を濁すと…

def cross_product(*arrays)
  if arrays.length == 1
    arrays.first.map{|x| [x]}
  else
    cross_product(*arrays[1..-1]).inject([]) {|result, x|
      result.concat arrays.first.map{|a| [a, *x] }
    }
  end
end

cross_product [1,2,3,4], %w[a b c]  # => [[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], %w[a b], ["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"]]

文字列を1文字ずつ無理矢理取り出すにはこんな細工をする。

class Array
  alias :_by_element :to_a
end

class String
  def _by_element
    split(//)
  end
end

def cross_product(*sequences)
  if sequences.length == 1
    sequences.first._by_element.map{|x| [x]}
  else
    cross_product(*sequences[1..-1]).inject([]) {|result, x|
      result.concat sequences.first._by_element.map{|a| [a, *x] }
    }
  end
end

cross_product [1,2,3,4], %w[a b c]  # => [[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"]]

リストの数固定して、Dynamicを使うというのを書いてみました。

import Data.Dynamic

crossProduct2 :: (Typeable a, Typeable b)
              => [a] -> [b] -> [(a,b)]
crossProduct2 ps qs 
 = map tuple 
 $ sequence 
 $ [ map toDyn ps
   , map toDyn qs
   ]
 where tuple [p,q]
        = ( fromDyn p undefined
          , fromDyn q undefined
          )

crossProduct3 :: (Typeable a, Typeable b, Typeable c)
              => [a] -> [b] -> [c] -> [(a,b,c)]
crossProduct3 ps qs rs
 = map tuple 
 $ sequence 
 $ [ map toDyn ps
   , map toDyn qs
   , map toDyn rs
   ]
 where tuple [p,q,r]
        = ( fromDyn p undefined
          , fromDyn q undefined
          , fromDyn r undefined
          )

crossProduct4 :: (Typeable a, Typeable b, Typeable c, Typeable d)
              => [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
crossProduct4 ps qs rs ss
 = map tuple 
 $ sequence 
 $ [ map toDyn ps
   , map toDyn qs
   , map toDyn rs
   , map toDyn ss
   ]
 where tuple [p,q,r,s]
        = ( fromDyn p undefined
          , fromDyn q undefined
          , fromDyn r undefined
          , fromDyn s undefined
          )

crossProduct5 :: (Typeable a, Typeable b, Typeable c, Typeable d, Typeable e)
              => [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
crossProduct5 ps qs rs ss ts
 = map tuple 
 $ sequence 
 $ [ map toDyn ps
   , map toDyn qs
   , map toDyn rs
   , map toDyn ss
   , map toDyn ts
   ]
 where tuple [p,q,r,s,t]
        = ( fromDyn p undefined
          , fromDyn q undefined
          , fromDyn r undefined
          , fromDyn s undefined
          , fromDyn t undefined
          )

-- Test data

data RGB = Red | Green | Blue  deriving (Typeable,Bounded,Enum,Show)
data ENWS = East | North | West | South deriving (Typeable,Bounded,Enum,Show)

allItem :: (Bounded a, Enum a) => [a]
allItem = [minBound..maxBound]

test = crossProduct4 (allItem::[()]) (allItem::[Bool]) (allItem::[RGB]) (allItem::[ENWS])

{-
*Main> putStr $ unlines $ map show $ test
((),False,Red,East)
((),False,Red,North)
((),False,Red,West)
((),False,Red,South)
((),False,Green,East)
((),False,Green,North)
((),False,Green,West)
((),False,Green,South)
((),False,Blue,East)
((),False,Blue,North)
((),False,Blue,West)
((),False,Blue,South)
((),True,Red,East)
((),True,Red,North)
((),True,Red,West)
((),True,Red,South)
((),True,Green,East)
((),True,Green,North)
((),True,Green,West)
((),True,Green,South)
((),True,Blue,East)
((),True,Blue,North)
((),True,Blue,West)
((),True,Blue,South)
-}

とりあえず御言葉に甘えて数字のみ対応。

function c = multisetcomb(varargin)
% return all combinations of items in given column vectors by picking up one
% item from each at once.
s1 = varargin{1};
s2 = varargin{2};
c = [repmat(s1,size(s2,1),1) sortrows(repmat(s2,size(s1,1),1))];
if length(varargin) > 2
    c = multisetcomb(c,varargin{3:end});
end

Arrayを拡張してみた。

Array.prototype.cartesianProduct = function(){
	if(!arguments.length) return this;
	var r = [], a = arguments[0], i, j, l;
	for(i = this.length, l = (a[0] ? a : a = [a]).length; i--;){
		if(!this[i][0]) this[i] = [this[i]];
		for(j = l; j--;) r[i * l + j] = this[i].concat(a[j]);
	}
	for(a = [], i = 1, l = arguments.length; i < l; i++) a[i - 1] = arguments[i];
	return arguments.callee.apply(r, a);
};
(this.WSH ? function($){ WSH.Echo($) } : alert)(
	[0, 1, 2, 3].cartesianProduct(["X", "Y", "Z"], [true, false], NaN).join("\n"));

Tuplesというそのままの関数があります．

see: Mathematica マニュアル - Tuples

In[1]:= Tuples[{{1, 2, 3, 4}, {"a", "b", "c"}}]

Out[1]= {{1, "a"}, {1, "b"}, {1, "c"}, {2, "a"}, {2, "b"}, {2, 
  "c"}, {3, "a"}, {3, "b"}, {3, "c"}, {4, "a"}, {4, "b"}, {4, "c"}}

In[2]:= Tuples[{{0, 1}, {"a", "b"}, {"foo", "bar"}}]

Out[2]= {{0, "a", "foo"}, {0, "a", "bar"}, {0, "b", "foo"}, {0, "b", 
  "bar"}, {1, "a", "foo"}, {1, "a", "bar"}, {1, "b", "foo"}, {1, "b", 
  "bar"}}

再帰で。

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])

二番煎じ。

1
2
3

crossProduct :: [[a]]->[[a]]
crossProduct [] = [[]]
crossProduct (x:xs) = [y:ys |y<-x, ys<-crossProduct xs]

問題を見ていて、何も正直にListの実体を作らなくてもいいのではないかと気付きました。そこでコンストラクタで与えた List の全組み合わせを表す List の実装を提示します。もちろん Java Collections Framework に基づいています。メモリの制約がないため、原理的には組み合わせの数がいくら増えても対応できますが、Java Collections Framework の制約から int の範囲を超えると例外を返すようにしました。

import java.util.*;

public class CombinationList extends AbstractList {
    private List[] sourceLists;
    private int size;
    private int[] ord;

    private class ElementList extends AbstractList {
        int[] indexs;
        ElementList(int[] is) {
            indexs = is;
        }
        public Object get(int index) {
            return sourceLists[index].get(indexs[index]);
        }
        public int size() {
            return sourceLists.length;
        }
    }

    public CombinationList(List... source) {
        sourceLists = source;
        ord = new int[source.length];
        long s = 1;
        for (int i = source.length - 1; i >= 0; i--) {
            ord[i] = (int)s;
            s *= source[i].size();
        }
        if (s > Integer.MAX_VALUE || s < 0) {
            throw new IllegalArgumentException("Source list too large");
        }
        size = (int)s;
    }

    public List get(int index) {
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException();
        }
        int[] indexs = new int[sourceLists.length];
        for (int i = 0; i < indexs.length; i++) {
            indexs[i] = index / ord[i];
            index %= ord[i];
        }
        return new ElementList(indexs);
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        System.out.println(new CombinationList(Arrays.asList(0, 1),
                                               Arrays.asList('a', 'b'),
                                               Arrays.asList("Foo", "Bar")));
    }
}</

DouKaku?

全ての組み合わせ

Posted feedbacks - Flatten