alle Kombinationen von Worten aus einer Liste von Listen finden, indem Sie 1 Wort aus jeder Liste mit Java ohne

Question

Rekursion

Gegeben: [["quick","lazy"],["brown","grey"],["fox","dog"]]

alle Kombinationen finden, indem nur 1 Wort aus jeder Liste der Wahl mit Hilfe von Java.

• Die Lösung für solche Liste der Listen funktionieren sollte
• beste Zeit Komplexität möglich
• ohne
Rekursion

Meine Lösung:

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

Hier sind zwei verschiedene Lösungen dazu. Für beide wurde die Eingabe erweitert, um zu zeigen, dass sie eine unterschiedliche Anzahl von Werten in jeder Unterliste verarbeiten kann.

Die erste Lösung berechnet die Gesamtzahl der Kombinationen und iteriert dann durch jede "nummerierte" Kombination und berechnet den zu verwendenden Wert aus jeder Unterliste. Diese Lösung sollte nur verwendet werden, wenn Unterlisten Array-basiert sind, da get(int index) verwendet wird, da andernfalls die Leistung beeinträchtigt wird.

Die zweite Lösung wird so offen wie möglich gemacht, d. H. Die äußere "Liste" kann irgendeine Collection sein, und "Unterlisten" können irgendeine Art von Iterable sein. Es erzeugt ein bisschen mehr Müll, da es Iteratoren neu erstellen muss, aber das sollte kein Problem sein (GC ist in diesen Tagen gut).

Für die Variation erzeugen die beiden Lösungen die Kombinationen in einer anderen Reihenfolge, aber sie können beide geändert werden, um es anders zu machen.

Lösung 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; 
} 

Lösung 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; 
    } 
} 

-Test

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

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

Ausgang 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

Versuchen Sie dies.

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