Kombinationen über rekursiven Algorithmus berechnen?

[ManInBlack]

Hallo,

ich bin auf der Suche, nach einem Algorithmus, der mir die Kombinationen von n-verschieden Arrays und n-verschiedenen Items berechnet.
Mein Tool läuft sonst grafisch basiert, ich habe hier zu Testzwecken ein konsolenbasiertes Tool geschrieben. Bei dem GUI-Tool stehen dem User verschiedenste Comboboxen, mit Möglichkeit der Mehrfachselektion, zur Verfügung.

Class Main:

package rekursion;

import java.util.ArrayList;
import java.util.List;

public class TestMain {
	
	/**
	 * Test-Main
	 * @param args
	 */
	public static void main(String[] args) {
		
		//object instancing
		TestMain testMain = new TestMain();
		
		//*******************************************************************
		//First parameter
		String [] selection1 = new String[3];
		selection1[0] = ("A1");
		selection1[1] = ("A2");
		selection1[2] = ("A3");
		
		testMain.setRpCollection(selection1);
		
//		//Second parameter
		String [] selection2 = new String[2];
		selection2[0] = ("B1");
		selection2[1] = ("B2");
		
		testMain.setRpCollection(selection2);
		
		//Third parameter
		String [] selection3 = new String[2];
		selection3[0] = ("C1");

		testMain.setRpCollection(selection3);
		
		//*******************************************************************
		
		Combinations.buildCombinations(0);
		
	}
	
	public void setRpCollection(String[] strArray) {
		
		List<String> arrayList = new ArrayList<String>();
		
		for (int i = 0; i < strArray.length; i++) {
			if (strArray[i] != null)
			{
			arrayList.add(strArray[i]);
			}
		}
		
		Combinations.setCombinations( arrayList);

	}


}

Class Combinations:

package rekursion;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Combinations {

	private static List<List<String>> allSelections;

	public static String buildCombinations( int ndx )
	{
		
		if( ndx >= allSelections.size() ){
			return "\n";
		}
		
		Iterator<String> iterator = allSelections.get(ndx).iterator();
		String result = "";
		while( iterator.hasNext() ){
			String part = (String) iterator.next();
			result = part + " " + buildCombinations( ndx + 1);
		System.out.println(result);
		}
		return result;
	}
	
	public static void setCombinations(List<String> arrayList) {
		
		// allSelections doesn´t exist and is empty
		if (allSelections == null) {
			allSelections = new ArrayList<List<String>>();
		}
		
		List<String> cacheList = new ArrayList<String>();
		
		for (String selectionItem : arrayList) {
			
			cacheList.add("Part_" + selectionItem);
			
		}
		allSelections.add(cacheList);
		
	}


}

Leider läuft es noch nicht so wie es soll.

Die Ergebnisliste sollte das lieferen:

Part_A1 Part_B1 Part_C1
Part_A1 Part_B2 Part_C1
Part_A2 Part_B1 Part_C1
Part_A2 Part_B2 Part_C1
Part_A3 Part_B1 Part_C1
Part_A3 Part_B2 Part_C1

Geht das überhaupt?

In meinem GUI-Tool befinden sich verschiedene Comboboxen mit verschiedenen Selections.
In diesem Test-tool sollen die selections (arrays) die Comboboxen repräsentieren.

Die Komplexität besteht darain, dass die Parameter und deren Selections n-verschieden sein können.

Vielleicht ist dies auch ganz einfach zu lösen, leider hab ich darin noch keine Idee,

Kann man mir bitte jemand helfen?

Vielen Dank

MfG
ManInBlack

 

[Marco13]

Wenn das Ziel ist, diese Kombinationen zu erstellen, schau dir mal http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html an.
Wenn das Ziel ist, diese Kombinationen unbedingt mit einem rekursiven Algorithmus zu erstellen, sag' nochmal bescheid.

 

[ManInBlack]

Hallo Marco,
vielen Dank für deine Antwort und den Link. Ich hab mir deinen beispiel-code angesehen,
aber leider komme ich derzeit, zur Lösung meiner Fragestellung, damit nicht zurecht.

Prinzipiell muss es nicht über einen rekursiven Algorithmus gelöst werden. Wenn es einen
alternativen Lösungsansatz gibt, wäre mir dieser ebenfalls sehr recht.

Nochmal kurz zur abstrakten Beschreibung meines Problems:

Man hat n-verschiedene Töpfe (z.B. 3) dort sind jeweils verschiedene Elemente enthalten.
Die einzelnen Elemente aus den Töpfen sollen jeweils mit den Elementen aus den anderen Töpfen kombiniert werden.
In der Statistik spricht man von einer Kombination mit Nicht-Beachtung der Reihenfolge und mit Zurücklegen.

TopfA enthält:
Kugel A1
Kugel A2
Kugel A3

TopfB enthält:
Kugel B1
Kugel B2

TopfC enthält:
Kugel C1

Die Ergebnisliste soll nun die Kombination (ohne Beachtung der Reihenfolge und mit Zurücklegen) enthalten:

Kugel A1, Kugel B1, Kugel C1
Kugel A1, Kugel B2, Kugel C1
Kugel A2, Kugel B1, Kugel C1
Kugel A2, Kugel B2, Kugel C1
Kugel A3, Kugel B1, Kugel C1

//Hinweis: Wenn nun die Anzahl der Kugeln der einzelnen Töpfe sich ändern, ändert sich auch die Ergebnisliste.
Genauso wie mit der Hinzufügung eines neuen Topfes (z.B. TopfD), dann wird Liste größer.

Ich hoffe ihr könnte es euch vorstellen. Derzeit hab ich keine Ahnung, wie ich an die Sache herangehen soll.

Wenn man meinem hinzugefügten Beispielcode ausführt, dann bekommt man von der Ergebnisliste leider nur das letzte Ergebnis zurückgeliefert. Hab auch schon viele andere Dinge ausprobiert, aber leider bisher ohne Erfolgt.

Gruß
ManInBlack

 

[0x7F800000]

Nochmal kurz zur abstrakten Beschreibung meines Problems:

Man hat n-verschiedene Töpfe (z.B. 3) dort sind jeweils verschiedene Elemente enthalten.
Die einzelnen Elemente aus den Töpfen sollen jeweils mit den Elementen aus den anderen Töpfen kombiniert werden.

solange diese "Töpfe" alle nur elemente einer Klasse beinhalten, gibt's kein problem. Wenn Typen unterschiedlich sind, hat man pech: in Java ist das nicht schön ausdrückbar. In Scala könnte man automatischen Code-generator anwerfen und ~22 verschiedene Klassen mit unterschiedlicher Anzahl der generics erstellen, das wäre aber auch äußerst hässlich. Mir ist bisher leider gar keine statisch typisierte sprache bekannt, die variable anzahl der generics erlauben würde. Das ist echt scheiße.

In der Statistik spricht man von einer Kombination mit Nicht-Beachtung der Reihenfolge und mit Zurücklegen.

Neneneneee... Lass mal statistik hier bloß weg: das ist ein stinknormales kartesisches Produkt was du beschreibst, wird in SQL & Co durch schlichtes Komma erzeugt^^ Nix statistik. Nur grundlegende Mengenlehre.

Für endliche Töpfe mit Elementen desselben Typs habe ich hier eine nicht zu schöne, aber für kleine Datensätze funktionsfähige Version:

/*
	 * example: buckets=[[A1,A2,..Aa],[B1,B2,..Bb],...,[X1,X2,..Xx]]
	 * the method will return an iterable that allows to iterate over all elements from Cartesian product
	 * [A1,A2,..Aa]x[B1,B2,..Bb]x[X1,X2,..Xx]
	 * that means it returns an iterator with all combinations:
	 * 
	 * [A1,B1,...X1]
	 * [A2,B1,...,X1]
	 * [A3,B1,...,X1]
	 * ...
	 * [A1,B2,...,X1]
	 * [A2,B2,...,X1]
	 * ...
	 * [Aa,Bb,...,Xx]
	 * 
	 * @param sets:			ordered List of collections of <T> structures
	 * @return:				Iterable of List<T> with all elements of cartesian product
	 */
	
	public static <T> Iterable<List<T>> finiteCartesianProduct(final List<Collection<T>> sets){
		return new Iterable<List<T>>(){
			private long size=1;
			{
				for(Collection<T> set:sets)size*=(long)set.size();
			}
			@Override
			public Iterator<List<T>> iterator() {
				return new Iterator<List<T>>(){
					long counter=0;
					ArrayList<T> currentValues=new ArrayList<T>(sets.size());
					ArrayList<Iterator<T>> iterators=new ArrayList<Iterator<T>>(sets.size());
					{
						for(Iterable<T> set:sets){
							Iterator<T> it=set.iterator();
							iterators.add(it);
							if(it.hasNext()){
								//if not, then the size is 0, hasNext is never true, set empty
								currentValues.add(it.next());
							}
						}
					}

					@Override
					public boolean hasNext() {
						return counter<size;
					}
					
					@Override
					public List<T> next() {
						List<T> result=new LinkedList<T>(currentValues);
						counter++;
						increment(0);
						return result;
					}
					
					private void increment(int i){
						if(iterators.get(i).hasNext()){
							currentValues.set(i,iterators.get(i).next());
						}else{
							iterators.set(i,sets.get(i).iterator());
							currentValues.set(i,iterators.get(i).next());
							if(i<iterators.size()-1){
								increment(i+1);
							}
						}
					}
					
					@Override
					public void remove() {
						throw new UnsupportedOperationException("impossible to change combination set");
					}
				};
			}
		};
	}

Bei Marco13's Sammlung habe ich übrigens nichts entsprechendes gefunden :bae: hehehehe^^

 

[Marco13]

Mit solchen Trivialitäten habe ich mich damals nicht aufgehalten. :smoke: 😉

 

[ManInBlack]

Super, danke euch beiden.

Ganz trivial finde ich es zwar nicht 🙂 aber genau das hab ich gesucht.

@Andrey
Eine Frage hätte ich noch an dich, warum ist denn deiner Meinung nach die Lösung nicht so "schön"?
Ich muss zugeben, dass ich bei deiner Lösung nicht ganz durchsteig 🙂

Wenn es noch weitere Lösungsansätze gibt, würden die mich sehr interessieren.

vg
ManInBlack

 

[0x7F800000]

Eine Frage hätte ich noch an dich, warum ist denn deiner Meinung nach die Lösung nicht so "schön"?

Weil da eine (theoretisch) unnötige einschränkung auf eine endliche Menge endlicher Mengen gemacht wird. Schlimmer noch:

for(Collection<T> set:sets)size*=(long)set.size();

...wegen dieser Sache funktioniert die Implementierung nicht mal für kartesische Produkte, die mehr als ~2^63 elemente haben, bzw. es ist eigentlich noch schlimmer: für sehr große Produkte funktioniert es nicht und meldet nicht mal Fehler.

Dagegen sind eigentlich kartesische Produkte von edit: endlich! vielen abzählbaren Mengen stets abzählbar. Nur krieg ich das in meinen Schädel irgendwie nicht rein, wie ich diese Diagonalisierung in Java ausdrücken soll... (von wegen trivial^^ 😉 ) Bei unendlichen Mengen muss man nämlich ganz anders, "in die breite statt in die tiefe" zählen, um alle kombinationen zu erwischen.
Für die Praxis ist das vielleicht aber wiederum nicht so schlimm, weil man bei ~10^9 durchgearbeiteten Einträgen pro sekunde etwa 300 jahre bräuchte, um alle 2^63 durchzuprobieren.

Aber für Supercomputer und Grids müsste man sich eben eine andere Implementierung einfallen lassen... Daher "nicht so schön" :bahnhof:

 

[Marco13]

Ah, jetzt wird's interessanter 😀
Dir schwebte also was vor wie

class CartesianProductIterator implements Iterator<Tuple>
{
    List<Iterator> delegates = ...
    Tuple next() 
    {
        return nextTupleMagicallyObtainedFrom(delegates);
    }

OK, DAS hat's in sich. Da wird man wohl irgendeine raumfüllende Kurve reinlegen müssen, vielleicht sowas wie eine Z-order (curve) - Wikipedia, the free encyclopedia - wie auch immer das gehen soll ... diese "delegate"-Iteratoren sind schon verdammt einbahnstraßig...Aber darüber könnte man man nachdenken...:reflect:

 

[0x7F800000]

Ah, jetzt wird's interessanter 😀
Dir schwebte also was vor wie

class CartesianProductIterator implements Iterator<Tuple>
{
    List<Iterator> delegates = ...
    Tuple next() 
    {
        return nextTupleMagicallyObtainedFrom(delegates);
    }

ne. Tuple müsste generisch parametrisiert sein. Und zwar durch eine variable anzahl von generics. das geht in Java nicht. In scala imitiert man dieses verhalten dadurch, dass Klassen Tuple0, Tuple1, Tuple2, ..., Tuple22 erzeugt wurden. Aber schön ist das auch nicht. Und ohne massiven Einsatz von Reflection würde man das auch dort nicht hinbekommen, und wenn überhaupt, dann maximal bis zum 22-fachen Produkt... Furchtbar.

OK, DAS hat's in sich. Da wird man wohl irgendeine raumfüllende Kurve reinlegen müssen, vielleicht sowas wie eine Z-order (curve) - Wikipedia, the free encyclopedia - wie auch immer das gehen soll ...

Hmm, naja... "raumfüllende" und "kurve" trifft's beides irgendwie nicht so genau. Ich wollte da eher klassisch da rangehen: Cantorsche Paarungsfunktion ? Wikipedia
war dann aber doch zu faul, das in java schön auszuformulieren^^

PS: hoppla, mit der Abzählbarkeit da oben habe ich mich ordentlich verschrieben: Abzählbare Produkte abzählbarer mengen sind natürlich nicht abzählbar, das Beispiel {0,1}x{0,1}x{0,1}x... ist ja genau das top-anwendungsbeispiel für's Cantor'sche Diagonalargument.
Aber endliche Produkte abzählbarer mengen sind abzählbar. Das ändere ich da oben jetzt^^ 😳

 

[Marco13]

Ja, diese "furchtbare" Tatsache, dass man nicht http://www.java-forum.org/allgemeine-java-themen/54824-beliebig-viele-typen-bei-generics.html verwenden kann, habe ich wohl oder übel schon antizipiert - dann verwendet man halt raw types 🙁 :bahnhof: Über die Scala'sche Lösung bin ich mal bei einem Blick über die API-Doku gestolpert, und fand, dass die schon SEHR nach einem krampfigen Workaround aussah - gut, in der Praxis ist das sicher praktisch, da kein Mensch dort mehr als Tuple22 braucht (warum eigentlich genau 22? ???:L ), aber "theoretisch" ist das eine Einschränkung der Sprache an sich, von der es schön wäre, wenn es sie nicht gäbe.

Dieses Cantordingens ist mir noch aus einschlägigen Vorlseungen bekannt - hatte sie aber etwas anders im Kopf, nämlich nicht als

   | 0   1   2   3   4    y
 --+----------------------->
 0 | 0   2   5   9  14   .
 1 | 1   4   8  13   .
 2 | 3   7  12   .
 3 | 6  11   .
 4 |10   .
   | .
 x v

sondern als

   | 0   1   2   3   4    y
 --+----------------------->
 0 | 0   2   3   9  10   .
 1 | 1   4   8  11   .
 2 | 5   7  12   .
 3 | 6  13   .
 4 |14   .
   | .
 x v

womit hoffentlich klar ist, warum ich dieses Aufzählungsschema irrtümlich nur als eine (von vielen) "raumfüllenden Kurven" angesehen hatte....

 

[0x7F800000]

Ja, diese "furchtbare" Tatsache, dass man nicht http://www.java-forum.org/allgemeine-java-themen/54824-beliebig-viele-typen-bei-generics.html verwenden kann, habe ich wohl oder übel schon antizipiert

Aaach, herrlich, generics rekursiv zu verschachteln war auch mein spontaner Einfall gewesen, als ich die Scala'sche Lösung gesehen habe (die mir auch nicht sonderlich gut gefallen hat)

Über die Scala'sche Lösung bin ich mal bei einem Blick über die API-Doku gestolpert, und fand, dass die schon SEHR nach einem krampfigen Workaround aussah - gut, in der Praxis ist das sicher praktisch, da kein Mensch dort mehr als Tuple22 braucht (warum eigentlich genau 22? ???:L ), aber "theoretisch" ist das eine Einschränkung der Sprache an sich, von der es schön wäre, wenn es sie nicht gäbe.

Krampfig: ja, aber für wen? Es ist zweifellos hässlich, aber diesen beschissenen code musste ja kein Mensch, sondern ein Programm schreiben, und jetzt ist das alles im pattern-matching komplett versteckt, sodass die benutzer davon gar nichts mitbekommen. 🙂 Und in der praxis dürften 22 reichen, bei mehr als 6 sollte man imho eh eine eigene "Ergebnistupelklasse" konstruieren, wo die einzelnen werte sinnvoll benannt werden, da ansonsten die gefahr zu groß wird, dass man die Positionen verdreht, und den Tupel falsch herum interpretiert.

Dieses Cantordingens ist mir noch aus einschlägigen Vorlseungen bekannt - hatte sie aber etwas anders im Kopf, nämlich nicht als

   | 0   1   2   3   4    y
 --+----------------------->
 0 | 0   2   5   9  14   .
 1 | 1   4   8  13   .
 2 | 3   7  12   .
 3 | 6  11   .
 4 |10   .
   | .
 x v

sondern als

   | 0   1   2   3   4    y
 --+----------------------->
 0 | 0   2   3   9  10   .
 1 | 1   4   8  11   .
 2 | 5   7  12   .
 3 | 6  13   .
 4 |14   .
   | .
 x v

womit hoffentlich klar ist, warum ich dieses Aufzählungsschema irrtümlich nur als eine (von vielen) "raumfüllenden Kurven" angesehen hatte....

Ja, die beiden varianten sind mehr oder weniger gleich, zu komplizierteren Mustern wie der Z-Kurve sollte man aber aus pragmatischen Gründen nicht greifen 😉