Algorithmus zur Kombination von Listenelementen

[andy]

Hallo,

ich suche einen Algorithmus, um aus einer Liste mit n Elementen alle möglichen Kombinationen der Reihe nach zu erstellen, wobei die Reihenfolge der Elemente nicht wichtig ist.

z.B: es gibt drei ArrayList mit unterschidlich n elementen

// list1 hat 3 elemente (Integer) 1, 2 und 3
 ArrayList<Integer> list1 = new ArrayList<Integer>();
       list1.add( new Integer(1) );
       list1.add( new Integer(2) );
       list1.add( new Integer(3) );

// list2 hat 2 elemente (Integer) 3, 5
ArrayList<Integer> list2 = new ArrayList<Integer>();
       list2.add( new Integer(3) );
       list2.add( new Integer(5) );

// list3 hat 2 elemente (Integer) 7, 8
 ArrayList<Integer> list3 = new ArrayList<Integer>();
       list3.add( new Integer(7) );
       list3.add( new Integer(8) );

Nun möchte ich alle möglichen Kombinationen der Elemente aus diese drei Listen haben.

Ergebniss sollte so aussehen:

1,3,7
2,3,7
3,3,7
1,5,7
2,5,7
3,5,7
1,3,8
2,3,8
3,3,8
1,5,8
2,5,8
3,5,8

also insgasammt 12 mögliche kombinationen.
elemente_der_list1 * elemente_der_list2 * elemente_der_list3 also 3*2*2 = 12 mögliche kombiantionen

Hat jemand eine Idee wie dieser Algorithmus auszuschauen hat, oder vielleicht existiert ein solches java programm schon???

vielen Dank

[JulianB]

1,3,7
2,3,7
3,3,7
1,5,7
2,5,7
3,5,7
1,3,8
2,3,8
3,3,8
1,5,8
2,5,8
3,5,8

Erinnert mich irgendwie an einen Bubblesort, google mal danach, das könnte klappen, wenn es das ist was du willst.

Liebe Grüße Julian.

[andy]

nein nein es hat nichts mit bubblesort zu tun.  bubblesort sortiert die Elemente EINE Liste. Ich möchte aber die elemente von n listen in allen Kombinationen haben.

[Daniel Thoma]

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