アイテムリストの要素を組み合わせの組み合わせに組み合わせる最も効率的な方法は？

Question

例えば、Stringのようないくつかの項目のリストを与えるとしましょう。

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の並行処理では、p241）、エデンGCは安いです。だから、私はオブジェクトの作成がJavaで安価であることを知っています。私の機嫌をとりなさい ：）。

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

これはどうでしょうか。

edit：明らかに、私は順列を作りたくありません。私はsizeof（リストのリスト）が大きいセットを作成したいです。

Answer 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; 
} 

Answer 2

これは、より効率的である：作品を数え、それをアプローチと同じ方法（各「位置」は、あなたのリストの一つであり、その位置に行くことができ、それぞれ「数字」はあなたのリストの要素である）：

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

（テストされていないが、いくつかのバグがあるかもしれないが、主なアイデアがある） 一般に、再帰は反復よりも遅いです。

Answer 3

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

リストの代わりにセットを使用する場合は、Sets.cartesianProductを使用できます。あなたが結果リストを反復するにつれて割り振られたゴミはまだ残っていますが、他のアプローチほどはそうではありません。

（あなたはSOのうち、コードの行数十を貼り付けるよりも、その中にもう少し自信を持つことができますので、一般的なライブラリー法として、それは非常に徹底的にテストされていますので注意してください。）

FYIがありましたa requestLists.cartesianProductでも同様ですが、私は誰もそれに取り組んでいるとは思わない。