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

単純に再帰で

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

問題を見ていて、何も正直に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 - Java

Index

Feed

Other

Link

Pathtraq