0

文字列など、いくつかのアイテムのリストのリストを提供しているとしましょう。

list 1: "a", "b", "c"

list 2: "d", "e", "f"

list 3: "1", "2", "3"


results: (a, d, 1), (a, d, 2), ... (c, f, 3)

（実際のユースケースは文字列などとは関係ありません。これは単なるモックアップです）

私はそれを行うための再帰的なメソッドを作成しましたが、それが投げられる一時的なセットをたくさん作成するので、私はそれに満足していません（ええ、オブジェクトの作成はJavaで安価であり、通常はCのmallocよりもCPU命令が少ないことを知っています（ソース：Java Concurrency in Action、p241）、eden GCは安い、何とか何とか何とか。ユーモアを交えて:)。

void combine(List<List<String>> itemLists, List<Set<String>> combinations, Set<String> partial) {
    if (itemLists == null || itemLists.isEmpty()) return;
    List<String> items = itemLists.get(0);
    for (String s : items) {
        Set<String> tmpSet = new HashSet<>(partial);
        tmpSet.add(s);
        if (itemLists.size() == 0) //termination test
            combinations.add(tmpSet);
        else
            combine(itemLists.subList(1, itemLists.size()), combinations, tmpSet);
    }
}

それで、あなたはこれについてどうしますか？

編集：明確にするために、私は順列を作成したくありません。sizeof（リストのリスト）が大きいセットを作成したい。

4

3 に答える 3

3

あなたが探しているのは「デカルト積」です。

リストの代わりにセットを使用しても問題がない場合は、を使用できますSets.cartesianProduct。結果のリストを反復処理するときに、まだいくらかのガベージが割り当てられています...しかし、他のアプローチほどではありません。

（一般的なライブラリメソッドとして、非常に徹底的にテストされているため、SOから数十行のコードを貼り付けるよりも少し自信を持って使用できることに注意してください。）

参考までに、要望もありLists.cartesianProductましたが、誰も取り組んでいないと思います。

于 2012-05-10T14:45:16.357 に答える
1

リストの数が可変であり、それらのリストのサイズも可変であると仮定して、提供された各リストから正確に1つの値を含む、すべての可能なセットのリストが必要です。正しい？

では、このようなものですか？

static List<Set<String>> combine(List<List<String>> itemLists)
{
    // Calculate how many combinations we'll need to build
    int remainingCombinations = itemLists.get(0).size();
    for(int i=1; i<itemLists.size(); i++)
    {
        remainingCombinations *= itemLists.get(i).size();
    }

    List<Set<String>> allSets = new ArrayList<Set<String>>();

    // Generate this combination
    for (;remainingCombinations > 0; remainingCombinations --)
    {
        Set<String> currentSet = new HashSet<String>();
        int positionInRow = remainingCombinations;

        // Pick the required element from each list, and add it to the set.
        for(int i=0; i<itemLists.size(); i++)
        {
            int sizeOfRow = itemLists.get(i).size();
            currentSet.add(itemLists.get(i).get(positionInRow % sizeOfRow));
            positionInRow /= sizeOfRow;
        }

        allSets.add(currentSet);
    }
    return allSets;
}
于 2012-05-09T01:14:48.057 に答える
1

これはより効率的です。カウントが機能するのと同じ方法でアプローチします（各「位置」はリストの1つであり、その位置に配置できる各「数字」はリストの要素です）。

List<Set<String>> combine( List<List<String>> input ){

    final int n = input.size();
    int[] index = new int[n];

    List<Set<Sting>> result = new List<>();

    int position = 0;
    while( position < n ){ // "overflow" check

        // Add set to result.
        Set<String> set = new HashSet<>();
        for( int i=0; i<n; i++ )
            set.add( input.get(i).get( index[i] ) );
        result.add( set );

        // Now the "hard" part: increment the index array
        position = 0;
        while( position < n ){

            if( index[ position ] < input.get( position ).size() ){
                index[position]++;
                break;
            }
            else // carry
                index[ position++ ] = 0;
        }
    }
    return result;
}

（テストされていません。いくつかのバグがある可能性がありますが、主なアイデアはそこにあります）。一般に、再帰は反復よりも遅くなります。

于 2012-05-09T01:14:58.563 に答える