考える再帰

Question

を使用せずにJavaを使用して、各リストから1つの単語を選択することによって、リストのリストから単語のすべての組み合わせを見つける： [["quick","lazy"],["brown","grey"],["fox","dog"]]

は、Javaを使用して、各リストから1つだけの単語を選択することで、すべての組み合わせを見つけます。

• ソリューションは、リスト
• 再帰

私のソリューションを使用せずに

可能な限り最高の時間の複雑さのいずれかのようなリストのために働く必要があります。ここでは

public static <T> Set<List<T>> getCombinations(List<List<T>> lists) { 
    Set<List<T>> combinations = new HashSet<List<T>>(); 
    Set<List<T>> newCombinations; 

    int index = 0; 

    // extract each of the integers in the first list 
    // and add each to ints as a new list 
    for(T i: lists.get(0)) { 
     List<T> newList = new ArrayList<T>(); 
     newList.add(i); 
     combinations.add(newList); 
    } 
    index++; 
    while(index < lists.size()) { 
     List<T> nextList = lists.get(index); 
     newCombinations = new HashSet<List<T>>(); 
     for(List<T> first: combinations) { 
      for(T second: nextList) { 
       List<T> newList = new ArrayList<T>(); 
       newList.addAll(first); 
       newList.add(second); 
       newCombinations.add(newList); 
      } 
     } 
     combinations = newCombinations; 

     index++; 
    } 

    return combinations; 
} 

Answer 1

は、二つの異なるソリューションがありますこれに。どちらの場合も、入力は各サブリスト内のさまざまな値を処理できることを示すために拡張されています。

最初の解決策は、合計の組み合わせ数を計算し、各「番号付き」組み合わせを繰り返し、各サブリストから使用する値を計算します。このソリューションは、サブリストが配列ベースの場合にのみ使用してください。get(int index)を使用しています。そうしないと、パフォーマンスが低下します。

第2の解決策は可能な限り開いている、すなわち外側の「リスト」は任意のCollectionとすることができ、「サブリスト」は任意の種類のIterableとすることができる。それはイテレータを再作成し続ける必要があるので、もう少しゴミを生成しますが、それは問題ではありません（最近のGCは良いです）。

変更のために、2つのソリューションは異なる順序で組み合わせを生成しますが、どちらの方法でも変更することができます。

溶液1

public static <T> List<List<T>> getCombinations(List<List<T>> valueSetList) { 
    int comboCount = 1; 
    for (List<T> valueSet : valueSetList) 
     comboCount = Math.multiplyExact(comboCount, valueSet.size()); // Fail if overflow 
    List<List<T>> combinations = new ArrayList<>(comboCount); 
    for (int comboNumber = 0; comboNumber < comboCount; comboNumber++) { 
     List<T> combination = new ArrayList<>(valueSetList.size()); 
     int remain = comboNumber; 
     for (List<T> valueSet : valueSetList) { 
      combination.add(valueSet.get(remain % valueSet.size())); 
      remain /= valueSet.size(); 
     } 
     combinations.add(combination); 
    } 
    return combinations; 
} 

溶液2

@SuppressWarnings("unchecked") 
public static <T> List<List<T>> getCombinations(Collection<? extends Iterable<T>> valueSetCollection) { 
    Iterable<T>[] valueSets = new Iterable[valueSetCollection.size()]; 
    Iterator<T>[] valueIters = new Iterator[valueSetCollection.size()]; 
    T[] values = (T[]) new Object[valueSetCollection.size()]; 
    int i = 0; 
    for (Iterable<T> valueSet : valueSetCollection) { 
     valueSets[i] = valueSet; // Copy to array for fast index lookup 
     valueIters[i] = valueSet.iterator(); 
     values[i] = valueIters[i].next(); // Fail if a wordSet is empty 
     i++; 
    } 
    List<List<T>> combinations = new ArrayList<>(); 
    NEXT_COMBO: for (;;) { 
     combinations.add(Arrays.asList(values.clone())); 
     for (i = values.length - 1; i >= 0; i--) { 
      if (valueIters[i].hasNext()) { 
       values[i] = valueIters[i].next(); 
       continue NEXT_COMBO; 
      } 
      valueIters[i] = valueSets[i].iterator(); 
      values[i] = valueIters[i].next(); 
     } 
     return combinations; 
    } 
} 

テスト

getCombinations(Arrays.asList(
     Arrays.asList("quick","lazy"), 
     Arrays.asList("brown","grey","black","red"), 
     Arrays.asList("fox","dog","wolf") 
)).forEach(System.out::println); 

出力1

[quick, brown, fox] 
[lazy, brown, fox] 
[quick, grey, fox] 
[lazy, grey, fox] 
[quick, black, fox] 
[lazy, black, fox] 
[quick, red, fox] 
[lazy, red, fox] 
[quick, brown, dog] 
[lazy, brown, dog] 
[quick, grey, dog] 
[lazy, grey, dog] 
[quick, black, dog] 
[lazy, black, dog] 
[quick, red, dog] 
[lazy, red, dog] 
[quick, brown, wolf] 
[lazy, brown, wolf] 
[quick, grey, wolf] 
[lazy, grey, wolf] 
[quick, black, wolf] 
[lazy, black, wolf] 
[quick, red, wolf] 
[lazy, red, wolf] 

出力2

[quick, brown, fox] 
[quick, brown, dog] 
[quick, brown, wolf] 
[quick, grey, fox] 
[quick, grey, dog] 
[quick, grey, wolf] 
[quick, black, fox] 
[quick, black, dog] 
[quick, black, wolf] 
[quick, red, fox] 
[quick, red, dog] 
[quick, red, wolf] 
[lazy, brown, fox] 
[lazy, brown, dog] 
[lazy, brown, wolf] 
[lazy, grey, fox] 
[lazy, grey, dog] 
[lazy, grey, wolf] 
[lazy, black, fox] 
[lazy, black, dog] 
[lazy, black, wolf] 
[lazy, red, fox] 
[lazy, red, dog] 
[lazy, red, wolf] 

Answer 2

はこれを試してみてください。

public static <T> Set<List<T>> getCombinations(List<List<T>> lists) { 
    int max = 1; 
    for (List<T> list : lists) 
     max *= list.size(); 
    Set<List<T>> result = new HashSet<>(max); 
    for (int i = 0; i < max; ++i) { 
     List<T> newSublist = new ArrayList<>(); 
     int n = i; 
     for (List<T> list : lists) { 
      int size = list.size(); 
      newSublist.add(list.get(n % size)); 
      n /= size; 
     } 
     result.add(newSublist); 
    } 
    return result; 
}