Daniel Thoma: Algorithmus zur Kombination von Listenelementen

Beitrag lesen

Hallo andy,

Ein Problem, dass sich sehr einfach rekursiv lösen lässt.
Dazu überlegt man sich, wie kann ich das Problem auf ein gleichartiges, kleineres Problem reduzieren.

Du kannst die Kombinationen aller n Listen erzeugen, indem Du jeden Eintrag der ersten Liste mit allen Kombinationen für die restlichen n - 1 Listen kombinierst. Überlegen muss man sich noch, wie der Rekursionsanfang aussieht. Entweder nimmt man dafür den Fall mit nur einer Liste (bei der die möglichen Kombinationen natürlich jeweils Listen mit den einzelnen Elementen sind) oder den Fall ohne eine Liste (dabei gibt es eine mögliche Kombination, die leere Liste). Ich habe mich für letztere Variante entschieden, da sie etwas allgemeiner und damit weniger Fehleranfällig ist.

Als Algorithmus:

  
public <E> List<List<E>> combine(Iterator<? extends List<E>> lists) {  
  if (!lists.hasNext()) {  
    return Collections.singeltonList(Collections.emptyList());  
  }  
  List<E> list = lists.next();  
  List<List<E>> combinations = combine(list);  
  List<List<E>> result = new ArrayList<List<E>>();  
  for (E element: list) {  
    for (List<E> combination: combinations) {  
      List<E> temp = new ArrayList<E>();  
      temp.add(element);  
      temp.addAll(combination);  
      combinations.add(temp);  
    }  
  }  
  return result;  
}  

Aufzurufen wäre das so:

  
List<List<Integer>> lists = new ArrayList<List<Integer>>();  
lists.add(list1); lists.add(list2); lists.add(list3);  
List<List<Integer>> combinations = combine(lists.iterator());  

Ich bin nicht ganz sicher, ob der Compiler die Typparameter für "Collections.singeltonList(Collections.emptyList())" automatisch bestimmen kann, evtl. muss man diese noch explizit angeben.

Grüße

Daniel