Kombinationen von ArrayListen mit unterschiedlichen Längen

[CroniD]

Morgen,

ich arbeite zur Zeit an einem verzwickten Algorithmus.
Dieser soll Objekte mit einander kombinieren. Dabei ist zu beachten, dass die Objekte in einer bestimmten Reihenfolge gegeben sind, geordnet nach einem Objektkriterium.
Sprachlich formuliert sieht meine Lösung erstmal folgendermaßen aus:

1. Absteigende Sortierung (QuickSort) der Objekte in einem Array nach einem Objektkriterium
2. Prüfung, ob es Objekte mit dem gleichen Objektkriterium gib in der Sortierung
   1. Wenn false, dann gebe das Array direkt zurück und beende den Algorithmus
   2. Wenn true, dann weiter bei 3.
3. Finde alle Objekte mit gleichem Objektkriterium und speichere sie jeweils in einer neuen ArrayList
4. Berechne die Anzahl an möglichen Kombinationen
5. Generiere Permutationen einer jeden neuen ArrayList (aus 3.)
6. Kombinierte die Ergebnisse aus 5. mit einander
7. Gebe das Ergebnis zurück und beende den Algorithmus

Okay, ich denke der Ablauf ist soweit i.O. für die zu erfüllende Aufgabe. Nun bisschen Quellcode.

Hier das zu betrachtende Objekt. Das angesprochende Objektkriterium ist "j_prio". TJob hat zwar noch weitere Werte, aber die beiden reichen.

public class TJob {
	
	private int j_id;
	private int j_prio;
	
	public TJob(int id, int prio) {
		setID(id);
		setPrio(prio);
	}
	
	public int getID() {
		return j_id;
	}
	
	public int getPrio() {
		return j_prio;
	}
	
	public void setID(int id) {
		j_id = id;
	}
	
	public void setPrio(int prio) {
		j_prio = prio;
	}
}

Hier die Hauptklasse:

public class MchCombi {


	public enum Mode {
		ASC, DSC
	}

	private static List<TJob[]> tjob_list = new ArrayList<TJob[]>();

	private static void quickSort(TJob[] arr, int inf, int sup, Mode mode) {
		if (inf < sup) {
			int pivot = arr[(inf + sup) / 2].getPrio();
			TJob aux;
			int i = inf, j = sup;
			while (i <= j) {
				if (mode == Mode.DSC) {
					while (arr[i].getPrio() > pivot)
						i++;
					while (arr[j].getPrio() < pivot)
						j--;
				} else if (mode == Mode.ASC) {
					while (arr[i].getPrio() < pivot)
						i++;
					while (arr[j].getPrio() > pivot)
						j--;
				}
				if (i <= j) {
					aux = arr[i];
					arr[i] = arr[j];
					arr[j] = aux;
					i++;
					j--;
				}
			}
			if (j > inf)
				quickSort(arr, inf, j, mode);
			if (i < sup)
				quickSort(arr, i, sup, mode);
		}
	}

	private static boolean equalCheck(TJob[] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				if (arr[i].getPrio() == arr[j].getPrio() && arr[i].getID() != arr[j].getID()) {
					return true;
				}
			}
		}
		return false;
	}

	private static void findPossibilities(TJob[] arr) {
		// 3. Finde alle Objekte mit gleichem Objektkriterium und speichere
		//     sie jeweils in einer neuen ArrayList
		List<List<TJob>> equalPrio_list = new ArrayList<List<TJob>>(20);
		for (int i = 0; i < arr.length; i++) {
			List<TJob> equalPrio = new ArrayList<TJob>(arr.length);
			for (int j = 0; j < arr.length; j++) {
				if (arr[i].getPrio() == arr[j].getPrio()) {
					// Check, ob TJob bereits erfasst wurde
					if (!MchCombi.subListsContains(equalPrio_list, arr[j]))
						equalPrio.add(arr[j]);
				}
			}
			if (equalPrio.size() > 0)
				equalPrio_list.add(equalPrio);
		}

		// 4. Berechne die Anzahl an möglichen Kombinationen
		long count = 1L;
		List<Long> fac_list = new ArrayList<Long>(10);
		for (int i = 0; i < equalPrio_list.size(); i++) {
			fac_list.add(MchCombi.factorial(equalPrio_list.get(i).size()));
		}
		for (int i = 0; i < fac_list.size(); i++)
			count = count * fac_list.get(i);

		// 5. Generiere Permutationen einer jeden neuen ArrayList
		List<List<List<TJob>>> prio_list = new ArrayList<List<List<TJob>>>();
		for (int i = 0; i < equalPrio_list.size(); i++) {
			int[] indices;
			List<TJob> elements = equalPrio_list.get(i);
			List<List<TJob>> li = new ArrayList<List<TJob>>();
			PermutationGenerator x = new PermutationGenerator(elements.size());
			while (x.hasMore()) {
				indices = x.getNext();
				List<TJob> tj_list = new ArrayList<TJob>(10);
				for (int j = 0; j < indices.length; j++)
					tj_list.add(elements.get(indices[j]));
				li.add(tj_list);
			}
			prio_list.add(li);
		}
		
		// 6. Kombinierte die Ergebnisse aus 5. mit einander
	}

	private static boolean subListsContains(List<List<TJob>> mainList, TJob tjob) {
		for (int i = 0; i < mainList.size(); i++) {
			for (int j = 0; j < mainList.get(i).size(); j++) {
				if (mainList.get(i).get(j).getID() == tjob.getID())
					return true;
			}
		}
		return false;
	}

	private static long factorial(int n) {
		long factorial = 1;
		for (int i = 1; i <= n; i++)
			factorial = factorial * i;
		return factorial;
	}

	public static void main(String[] args) {
		// Testwerte
		TJob[] arr = { new TJob(0, 7),
					   new TJob(1, 6),
					   new TJob(2, 6),
					   new TJob(3, 5),
					   new TJob(4, 3),
					   new TJob(5, 3) };
		MchCombi.quickSort(arr, 0, arr.length-1, Mode.DSC);
		if (MchCombi.equalCheck(arr))
			MchCombi.findPossibilities(arr);
		else
			MchCombi.tjob_list.add(arr);
		
		//MchCombi.print(tjob_list);
	}
}

PermutationGenerator Klasse -> Permutation Generator
Die "print(tjob_list)" Methode habe ich weggelassen, weil sie nichts mit dem Algorithmus zu tun hat.

Dann noch ein kleines Beispiel wie das ganze Arbeiten soll.

geg. sind 6 TJob Objekte, die jeweils folgende j_prio Werte haben
und in einem Array zusammengefasst sind:
TJob1(7), TJob2(6), TJob3(6), TJob4(5), TJob5(3) und TJob6(3)

Absteigende Sortierung durch QuickSort liefert als Ergebnis:
TJob1(7), TJob3(6), TJob2(6), TJob4(5), TJob6(3), TJob5(3)

Wie man gleich sehen kann, gibt es TJobs, die die gleiche j_prio
aufweisen. Diese jeweils in eine eigene ArrayListe packen:
ArrayList1 ( TJob1(7) )
ArrayList2 ( TJob3(6), TJob2(6) )
ArrayList3 ( TJob4(5) )
ArrayList4 ( TJob6(3), TJob5(3) )

Nun Permutationen aus den Elementen in den neuen ArrayListen
bilden, die mehr als 1 Element besitzen:
ArrayList1 ( ArrayListe1( TJob1(7) ) )
ArrayList2 ( ArrayListe1( TJob3(6), TJob2(6) ),
             ArrayListe2( TJob2(6), TJob3(6) ) )
ArrayList3 ( ArrayListe1( TJob4(5) ) )
ArrayList4 ( ArrayListe1( TJob6(3), TJob5(3) ),
             ArrayListe1( TJob5(3), TJob6(3) ) )

Nun diese ArrayListen kombinieren unter Einhaltung der Reihenfolge.
Es sollten dann 4 Kombinationen rauskommen:
Kombination 1: ArrayList( TJob1(7), TJob3(6), TJob2(6), TJob4(5), TJob6(3), TJob5(3) )
Kombination 2: ArrayList( TJob1(7), TJob2(6), TJob3(6), TJob4(5), TJob6(3), TJob5(3) )
Kombination 3: ArrayList( TJob1(7), TJob3(6), TJob2(6), TJob4(5), TJob5(3), TJob6(3) )
Kombination 4: ArrayList( TJob1(7), TJob2(6), TJob3(6), TJob4(5), TJob5(3), TJob6(3) )

Ja, also ihr seht es bereits am Quellcode. Punkt 6. auf der Liste ist noch nicht implementiert. Ich hatte es zu erst versucht die einzelnen ArrayListen auf eine gleiche Elementanzahl zu bringen, in dem ich deren eigenen Inhalt so lange selbst eingefügt habe bis die Elementanzahl der Anzahl der TJob Objekte entsprach (was auch recht einfach ging). Problem wurde dann darauf folgend, wenn ich nun die Listen in eine neue Liste durch eine for-Schleife zusammen packen wollte, dann sah das Ergebnis folgendermaßen aus:

Kombination 1: TJob1(7) TJob3(6) TJob2(6) TJob2(6) TJob3(6) TJob3(6) TJob2(6) TJob2(6) TJob3(6) TJob4(5) TJob4(5) TJob4(5) TJob4(5) TJob6(3) TJob5(3) TJob5(3) TJob6(3) TJob6(3) TJob5(3) TJob5(3) TJob6(3)  
Kombination 2: TJob1(7) TJob3(6) TJob2(6) TJob2(6) TJob3(6) TJob3(6) TJob2(6) TJob2(6) TJob3(6) TJob4(5) TJob4(5) TJob4(5) TJob4(5) TJob6(3) TJob5(3) TJob5(3) TJob6(3) TJob6(3) TJob5(3) TJob5(3) TJob6(3)  
Kombination 3: TJob1(7) TJob3(6) TJob2(6) TJob2(6) TJob3(6) TJob3(6) TJob2(6) TJob2(6) TJob3(6) TJob4(5) TJob4(5) TJob4(5) TJob4(5) TJob6(3) TJob5(3) TJob5(3) TJob6(3) TJob6(3) TJob5(3) TJob5(3) TJob6(3)  
Kombination 4: TJob1(7) TJob3(6) TJob2(6) TJob2(6) TJob3(6) TJob3(6) TJob2(6) TJob2(6) TJob3(6) TJob4(5) TJob4(5) TJob4(5) TJob4(5) TJob6(3) TJob5(3) TJob5(3) TJob6(3) TJob6(3) TJob5(3) TJob5(3) TJob6(3)

Der Grund ist mir durchaus bewusst, so nach mehr stündigem Überlegen, allerdings fällt mir sonst nichts weiter ein. Könntet ihr mir eine Möglichkeit aufzeigen?

 

[miwoe]

Ist eigentlich nicht schwer:

Arraylisten mit permutationen durchlaufen und nebenbei kombinationen aufbauen.

Arraylist1 hat nur ein Element, also gibt es nur eine Kombination mit dem Element.

Arraylist2 hat nun zwei Elemente, also muss die bisherige Kombination geklont werden und jeder dieser Kombination erhält jeweils ein Element aus Arraylist2

u.s.w.u.s.f

geht wahrscheinlich am Besten rekursiv, durch die Methodendefinition

public ArrayList konkateniere(ArrayList<ArrayList> restListe, ArrayList zwischenergebnis);

Rekursiv:
Anzahl Permutationen aus nächstem Element der restListe entnehmen, zwischenergebnis Anzahl mal klonen und jedem Satz je eine Permutation zuordnen, danach, wenn noch Elemente in restListe erhalten, erneut konkateniere aufrufen mit restliste und neuem Zwischenergebnis "füttern". Dieses Ergebnis zurückgeben. Wenn keine Element mehr in der restliste, dann das neue Zwischenergebnis (Endergebnis) zurückgeben.


Kann aufwändig werden, aber das ist Konkatenation nunmal....

 

[CroniD]

Rekursiv:
Anzahl Permutationen aus nächstem Element der restListe entnehmen, zwischenergebnis Anzahl mal klonen und jedem Satz je eine Permutation zuordnen, danach, wenn noch Elemente in restListe erhalten, erneut konkateniere aufrufen mit restliste und neuem Zwischenergebnis "füttern". Dieses Ergebnis zurückgeben. Wenn keine Element mehr in der restliste, dann das neue Zwischenergebnis (Endergebnis) zurückgeben.

Eine Rekursion ist eher unpraktisch, weil die Anzahl an TJobs variable ist und die Anzahl an TJobs mit gleichen "Prio"-Wert nicht bekannt ist vor dem Algorithmus. Es könnten sich dann sehr viele Permutationen ergeben und die Rekursion könnte ziemlich schnell den Speicher zu knalln, oder?
Ich muss dazu sagen, dass ich Rekursionen eher vermeide und daher noch nie häufig angewandt habe.

Aber ich habe es nun doch anders gelöst. Mein erster Ansatz war im Prinzip richtig, nur hatte ich vergessen, dass das die kopierten Listen selbst Elemente enthalten, die mit den wiederrum kopierten Listen verknüpft sind (eine Änderung wurde also mehrmals erfasst). Gut, dann habe ich meine TJobs direkt kopiert und siehe da: es geht.

Hier der Quellcode für die jenigen, die es noch interessiert (Ausschnitt aus der Klasse "MchCombi"):
[JAVA=96]
// 6. Kombinierte die Ergebnisse aus 5. mit einander
// 6.1 Bringe alle ArrayListen auf die gleiche Länge
List<List<List<TJob>>> tmp = new ArrayList<List<List<TJob>>>();
List<List<TJob>> tmp_list1;
List<TJob> tmp_list2;
for (int i = 0; i < prio_list.size(); i++) {
tmp_list1 = new ArrayList<List<TJob>>();
while (tmp_list1.size() < count) {
// Sicherstellen, dass jede Liste so viele Elemente wie Kombinationen
// besitzt
for (int j = 0; j < prio_list.get(i).size(); j++) {
tmp_list2 = new ArrayList<TJob>();
for (int k = 0; k < prio_list.get(i).get(j).size(); k++) {
TJob tj = prio_list.get(i).get(j).get(k);
tmp_list2.add(tj);
}
tmp_list1.add(tmp_list2);
}
}
tmp.add(tmp_list1);
}

// 6.2 Setze die Daten zusammen in eine Liste
List<TJob[]> final_list = new ArrayList<TJob[]>((int) count);
TJob[] final_tj_list = new TJob[arr.length];
int index = 0;

for (int i = 0; i < count; i++) { // final_list size
for (int j = 0; j < tmp.size(); j++) {
for (int k = 0; k < tmp.get(j).get(i).size(); k++) {
TJob tj = tmp.get(j).get(i).get(k);
final_tj_list[index] = tj;
index++;
}
}
final_list.add(final_tj_list);
final_tj_list = new TJob[arr.length];
index = 0;
}

// 6.3 Speichere die Liste in tjob_list
MchCombi.tjob_list.addAll(final_list);
[/code]

Trotzdem danke für die fixe Antwort miwoe.

 

[miwoe]

Hum, ist eine interessante Frage, ob die Rekursion den Speihcer vollknallen würde.

Mein erster Gedanke ist eigentlich nein, da ja nur Objektereferenzen kopiert würden, jedoch keine Objekte selbst. Muss ich mal kommenden Urlaub ausprobieren

Aber schön, dass es jetzt bei dir funktioniert.

 

[CroniD]

Na ja, eine Rekursion belegt immer mehr Speicher als eine Iteration, wegen den Funktionsaufrufen, so weit ich mich noch erinnern kann.

Die Anzahl der benötigten Funktionsaufrufe ist in diesem Fall an die Anzahl der zu kombinierenden Listen gebunden. Zum Beispiel kann der Fall eintreten, dass der Algorithmus 30 TJob Objekte bekommt, wovon vielleicht 5 eine Prio mit 1, 4 mit 2, 8 mit 3 usw. haben. Alle TJob Objekte mit gleicher Prio müssen dann durch den PermutationsGenerator gejagt werden, wobei die Anzahl der Ergebnise "n!" bestimmt ist. Dann diese ganzen Listen kombinieren, wobei diese Kombinationsanzahl bestimmt ist durch ein Produkt aus den Listenelementen von Liste A mal den Listenelementen der nächsten Liste B usw. Also in der Theorie würde ich sagen: verdammt viele Kombinationsergebnisse.

Zum Beispiel bei 10 TJobs, wobei 5 TJobs die gleiche Prio und 3 die gleiche Prio haben macht das ganze schon 5! * 3! = 126 mögliche Kombinationen.

Die Rekursion würde jede Kombination durch einen erneuten Funktionsaufruf bilden. Na ja, also die Grenze des Heap Space erreicht man definitiv schnell denke ich. Nicht wegen den Objekten, sondern wegen den Aufrufen selbst. Oder gehe ich da mit den falschen Annahmen ran?

 

[maki]

Bei Rekursion (so wie bei allen Methodenaufrufen) geht es um den Stack, nicht um den Heap, lässt sich mitteln XSS VM Parameter steuern, unter windows git es da einen Bug, da muss man einen neuen Thread starten um in den Genuss des Xss Parameters zu kommen.

Rekursion vs. Iteration ist 'ne alte Kiste, das erste drückt best. Dinge sehr elegant aus, das letztere spart Stack & Methodenaufrufe, persönlich würde ich immer Rekursion bevorzugen falls möglich.

 

[CroniD]

Oh, dann entschuldigung, dass ich das durcheinander geworfen habe. Dachte bisher immer, dass der Stack zum Heap gehört. Okay.

Allerdings bleibt das Problem ja trotzdem, dass diese Rekursion, dann sehr oft aufgerufen werden könnte. Den Stack zu vergrößern wäre eine Maßnahme.

BTW Falls es von Interesse ist: Der Algorithmus ist letzten Endes die Basis für einen Maschinenbelegungsplan einer Software. Die Ergebnisse dienen zwar nur für eine Simulation, aber dennoch sind Fälle möglich bei denen mehr als 300 "TJobs" pro Maschine verbucht sind. Na ja, ich muss den Algorithmus definitiv noch optimieren, viele Listen sind bspw. eigentlich unnötig.

Rein aus Interesse meinerseits: Wenn ich nun den Fokus auf gut lesbaren Code legen würde, dann eher eine Rekursion und wenn der Algorithmus performant (Speicher, Laufzeit usw.) sein soll eher interativ?

 

[maki]

Rein aus Interesse meinerseits: Wenn ich nun den Fokus auf gut lesbaren Code legen würde, dann eher eine Rekursion und wenn der Algorithmus performant (Speicher, Laufzeit usw.) sein soll eher interativ?

Ja.