Java Kombinationen beliebiger Größe berechnen

[Helios co.]

Hallo @all,

ich stehe vor einem nicht ganz so trivialen Problem, denke ich.

Für ein Array (int) mit beispielsweise 50 Einträgen von 0,1,2,3,...,49 möchte ich alle möglichen Kombinationen beispielsweise der Größe 10 berechnen. Also 0 1 2 3 4 5 6 7 8 9,
0 1 2 3 4 5 6 7 9 10, 0 1 2 3 4 5 6 7 9 11 bis 49 49 49 49 49 49 49 49 49 49

Ich habe zwar eine Lösung, die jedoch extrem rechenintensiv ist und meinen Rechner in die Knie zwingt.

Hat jemand hier Erfahrung mit derartigen Problemen und kann mir weiterhelfen?

Danke im Voraus!

 

[Alberto866]

Kannst du bitte deinen Code hier posten - dann sehen wir, was du schon getan hast.

Ansonsten: Kann schon sein, dass das deinem Rechner schwer fällt, ist ja auch eine recht komplexe Berechnung

 

[ghozt]

Du musst extrem viele Kombinationen eintragen, das kann nicht schnell gehen aber ja, poste deinen Code

 

[yoT!mO]

Klar zwingt das deinen Rechner in die Knie, das wären dann ja auch 50^10 Kombinationen.
Wenn du einen Mehrkernprozessor hast, kannstdu optimieren, indem du bestimmte Kombinationen parallel berechnen lässt, also mit Multi-Threading.
Sequenziell fällt mir auch keine andere Möglichkeit ein, als praktisch einfach jede Stelle des Feldes von 0 bis 49 hochzuzählen und dann die daraus resultierende 10-stellige Zahl irgendwo zu speichern.

Gruß Timo

 

[DjNDB]

Hat das für dich einen praktischen Zweck, oder ist das einfach nur eine Übungsaufgabe?

 

[Killkrog]

Solche "Rucksack-Packen"-Methoden haben immer ätzende Laufzeiten (2^n).
Wenn bei dir das Array sortiert ist, kannst du ein paar Kniffe einbauen, damit es schneller wird.

 

[Turas]

Wie yoT!mO schon sagte, es sind insgesamt 50^10 Möglichkeiten, da bringt auch paralleles rechnen nichts mehr. Es ist hoffnungslos.

(Außer du hast viele Tage Rechenzeit für sowas übrig)

 

[yoT!mO]

Naja mit Parallelem Rechnen könnte man bestimmt irgendwas um den Faktor 2-3 (bei 4 Kernen) an Beschleunigung rausholen.
Wenn zB ein Master die Ergebnismenge in die Anzahl Kerne aufteilt, und zB Worker-Thread 1 den Zahlenbereich von
0 0 0 0 0 0 0 0 0 0 bis 12 49 49 49 49 49 49 49 49 49 berechnet, während Worker-Thread 2 den Bereich von
13 0 0 0 0 0 0 0 0 0 bis 25 49 49 49 49 49 49 49 49 49 berechnet usw. sollte das doch einen gewissen Performance-Schub geben, als wenn nur ein Kern den ganzen Wertebereich abklappern muss, oder?

Gruß Timo

 

[NullPointer]

Ja, klar. Die Frage ist, ob der Schub reicht, um in akzeptabler Zeit fertigzuwerden

 

[Helios co.]

public String[] berechneKombinationen(int k, int[] values){

		//1. Berechnung der Anzahl der möglichen Kombinationen
		int anzahlCombis = values.length;
		for(int i = 0; i < k-1; i++){

			anzahlCombis*=values.length;
		}
		System.out.println("Anzahl der Kobinationen: " +anzahlCombis);



	
		int spalte1 = anzahlCombis / values.length;
		Vector v = new Vector(); 
		v.add(spalte1);

		while(spalte1 / values.length > 1){
			v.add(spalte1 / values.length);
			spalte1 = spalte1 / values.length;
		}
		v.add(1); 



		//3. Füllen mir leeren Strings
		String[] combis = new String[anzahlCombis];
		for(int i = 0; i < combis.length; i++){
			combis[i] = "";
		}


		//4. Berechnung der Kombinationen
		Iterator it = v.iterator();
		while(it.hasNext()){

			int sprungMarke = (Integer)it.next();
			int valuesMarker = 0;
			int counter = 0;

			for(int i = 0; i < anzahlCombis; i++){

				combis[i] += ""+values[valuesMarker]+" ";

				counter++;
				if(counter >= sprungMarke){
					counter = 0;

					if(valuesMarker < values.length-1){
						valuesMarker++;
					}
					else{
						valuesMarker = 0;
					}
				}
			}	
		}
		return combis;
	}

Das ist der code den ich mir zur späten Stunde ausgedacht habe. Für Kombinationen der Größe 5 geht er sogar noch flott, darüber hinaus wird es aber eng.

Mir ist leider keine einfache rekursive Lösung eingefallen.

Ich habe zumindest theoretisch 16 Kerne mit 72GB RAM zur Verfügung, d.h. Threading könnte wirklich was bringen. Ich habe allerdings mit Multithreading noch kaum zutun gehabt.

 

[NullPointer]

Das liegt eben an dem extrem exponentiellen Aufwand der Berechnung. Jedes Mal, wenn du died Länge der Kombinationen um 1 erhöhst, hast du (values.length)mal - also in deinem Beispiel 50x - so viele Kombis wie vorher.

Die Berechnung von anzahlCombis kannst du übrigens einfacher mit Math.pow() machen. Im übrigen hast du ein Problem: 50^10 paßt nicht ansatzweise in eine "int"-Variable rein, nur in einen "long".

Nachtrag: Mußt du die Zahlen schon während der Berechnung in Strings umwandeln? Das halte ich für nicht gut für die Performance.

 

[Helios co.]

Jap, leider. Noch schlimmer: das wofür ich diese Kombinationen brauche ist alles in allem ein NP-vollständiges Problem.

Könntet ihr mir einpaar Code-Hinweise bezüglich der Multithreading Implementierung geben?

Ps. danke für den Tipp mit Math.pow!

 

[yoT!mO]

Ich sitz grad im Zug, aber wenn ich zuhause bin, kann ich ja mal einen groben Entwurf fürs Multi-threading posten.
Gruß Timo

 

[Helios co.]

Prima, danke dir dafür im Voraus!

 

[Tumbleweed]

Du solltest unbedingt einen StringBuilder verwenden statt mit Strings zu hantieren. Da wird bei jedem concatenate ein neuer String erzeugt im Hintergrund und das ist teuer.

 

[DonnyDepp]

du willst ein object "combis", dass dir die x.te kombination als string zurückgibt?
z.b. combis.get(2345) := "0 12 23 34 1 9 7 8 9 2"
??

musst du denn zwangsweise alle kombinationen im speicher halten?
brauchst du jede der kombination für den späteren verlauf mehrmals?

sonst erstell dir doch eine klasse, die ein array von arrays (matrix) initialisiert, und dir über ne getmethode die matrixposition zurückgibt.

array: a[b1 b2 b3 b4 b5 b6 b7 b8 b9 b10]
b1: [0..49]
b2: [0..49]
etc.

und für die getmethode arbeitest dann mit modulo und div auf den jeweiligen b-arrays bezüglich ihrer position.


andererseits könntest auch deine schleifen anpassen, dass die mit einem einzigen:
for(int i = 0; i < anzahlCombis; i++) ...
-durchlauf für jede combi den string zusammenbastelt.

denn du hast mit dem int[] values[0..49] und k alle benötigten informationen.
wozu brauchst du dann den vector v?


im prinzip willst du doch nur eine natürliche zahl in ein anderes zahlensystem übertragen.
stell dir vor, wie du es für dezimal -> binär machen würdest.
da würdest auch nicht 50^10 binärzahlen im voraus berechnen.

 

[Funart]

In so einer Situation überlegt man sich ob sich der Aufwand lohnt alles vorher zu berechnen.
Gehen wir davon aus du brauchst von dem ganzen haufen nur 30 einträge.
Dann wirst du die 30 Einträge addhoc algorithmisch lösen und nicht per index auf die permuatation zugreifen.

Würder daher die Anstrengungen dahingehend legen die 10. permutation zu bekommen.

 

[yoT!mO]

So hier mal mein naiver Ansatz:

public class MasterThread extends Thread {

	private int[] array;
	private WorkerThread[] worker;
	private int nCPUs;

	public MasterThread(int[] array) {
		this.array = array;
		this.nCPUs = Runtime.getRuntime().availableProcessors();
		this.worker = new WorkerThread[nCPUs];
	}

	public void run() {
		for (int i = 0; i < this.worker.length; i++) {
			this.worker[i] = new WorkerThread(this.array, i
					* (this.max(this.array) / nCPUs), (i + 1)
					* (this.max(this.array) / nCPUs), 10);
		}

	}

	public int max(int[] array) {
		int max = 0;
		for (int i = 0; i < array.length; i++) {
			if (this.array[i] > max) {
				max = this.array[i];
			}
		}
		return max;
	}

}

public class WorkerThread extends Thread {
	
	private int[] array;
	private int start;
	private int end;
	private int[] tmpResultArray;
	private ResultHandler resultHandler;
	
	public WorkerThread(int[] array, int start, int end, int resultLength) {
		this.array = array;
		this.start = start;
		this.end = end;
		this.tmpResultArray = new int[resultLength];
		this.resultHandler = new ResultHandler(this.getCountOfCombinations(), resultLength);
	}
	
	public void run() {
		
		for (int i = start; i < end; i++) {
			
			tmpResultArray[0] = i;
			for (int j = tmpResultArray.length - 1; j > 0; j--) {
				for (int k = 0; k < array.length; k++) {
					tmpResultArray[j]++;
					this.resultHandler.addResultSet(tmpResultArray);
				}
				tmpResultArray[j] = 0;
			}
			
		}
	}
	public int getCountOfCombinations() {
		// return die Anzahl an Kombinationen, die mit this.start und this.end möglich sind
	}

}

Keine Ahnung, ob das so funktioniert, oder ob ich grad ein paar Denkfehler hab, aber von dem Grundgedanken her sollte es so ca. aussehen.

Gruß Timo

 

[IceMatrix]

Es gibt für das Problem keine effiziente Lösung. Wie du schon gesagt hast -> NP-vollständig. Die Anzahl der möglichen Kombinationen steigt exponentiell mit der Anzahl der Stellen. Egal wie du das implementierst.. es wird bei 10^50 extrem lange dauern (viele Jahre!). Das ist äquivalient mit Bruteforce auf einem 167-bit Schlüssel.

Vergiss es!

 

[DonnyDepp]

	public String getIndex(int i, int k, int[] values) {
		String result = "";
		int rest = i;
		for (int j = 0; j < k; j++) {
			result += values[rest % values.length] + " ";
			rest = rest / values.length;

		}
		System.out.println("i: " + i);
		System.out.println("result: " + result);

		return result;
	}

für 0 <= i < anzahlCombis