Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
--- Kombinatorik mit Rekursion (http://www.informatikerboard.de/board/thread.php?threadid=2912)


Geschrieben von Haevelin am 11.03.2016 um 12:41:

  Kombinatorik mit Rekursion

Ich soll die Kombination von drei Werten über eine Länge von 11 Werten darstellen. Das gibt 3 hoch 11 Kombinationen. Wie kann ich das programmieren? Ich möchte nicht nur die Kombination darstellen, sondern auch jede Kombination abspeichern. Bspw. bei zwei Werten über die Länge 2:
Werte a, b

Kombinationen:
a a
a b
b a
b b



Geschrieben von Haevelin am 11.03.2016 um 14:05:

  RE: Kombinatorik mit Rekursion

Folgenden Code habe ich erarbeitet:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
public ArrayList<ArrayList<Integer>> kombiniere(int behandlungszeit_1, int behandlungszeit_2, int behandlungszeit_3, ArrayList<ArrayList<Integer>> al_von_al, int laenge)
{
 		if (laenge >0){
 		ArrayList<ArrayList<Integer>> copy_al= al_von_al;
 		 al_von_al.clear();
 		for (int i=0; i< copy_al.size(); i++){
 			ArrayList<Integer> wert_1= copy_al.get(i);
 			wert_1.add(behandlungszeit_1);
 			ArrayList<Integer> wert_2= copy_al.get(i);
 			wert_1.add(behandlungszeit_2);
 			ArrayList<Integer> wert_3= copy_al.get(i);
 			wert_1.add(behandlungszeit_3);
 			al_von_al.add(wert_1);
 			al_von_al.add(wert_2);
 			al_von_al.add(wert_3);
 		}
 		 return kombiniere(behandlungszeit_1, behandlungszeit_2, behandlungszeit_3,  al_von_al,  laenge-1);
 		} else { return al_von_al;}
 		 		 	} 	



Geschrieben von eulerscheZahl am 11.03.2016 um 14:19:

 

Hier meine geistigen Ergüsse:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
package infoboard;

import java.util.ArrayList;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		ArrayList<int[]> tmp = new ArrayList<int[]>();
		comb(new int[] { 1, 2, 3 }, new int[11], 0, tmp);
		for (int[] permut : tmp) {
			System.out.println(Arrays.toString(permut));
		}
	}

	static void comb(int[] alphabet, int[] taken, int index, ArrayList<int[]> result) {
		if (index == taken.length) {
			result.add(Arrays.copyOf(taken, taken.length));
			return;
		}
		for (int next : alphabet) {
			taken[index] = next;
			comb(alphabet, taken, index + 1, result);
		}
	}
}



Geschrieben von Haevelin am 15.03.2016 um 16:41:

 

Ja, sehr instruktiv. Aber es gibt glaube ich auch eine iterative Lösung. Demnach iteriert man über eine gewisse Länge, die die Kombination hat und initialisiert zunächst in einer ArrayList von ArrayList al drei ArrayList mit den zu kombinierenden Werten. Dann kopiert man diese ArrayList von ArrayLists nach cp und macht ein al.clear. Dann iteriert man innerhalb der ersten Schleife über cp und fügt zu den ArrayLists jeweils einen Wert der drei Werte hinzu.



Geschrieben von eulerscheZahl am 15.03.2016 um 17:13:

 

Iterativ kannst du einfach in ein anderes Zahlensystem umrechnen. In deinem Beispiel ins 3er System.



Geschrieben von Haevelin am 16.03.2016 um 15:51:

 

Ja, danke; aber ich sehe drei Probleme:
1) Wie kodiere ich eine Zahl in das Termärsystem?
2) Wie fülle ich auf die gewünschte Stellenzahl mit 0 en auf?
3) Wie ordne ich den Zahlen 0,1,2 des Dreiersystems die Zahlen 15,20,30 zu um diese Kombinationen darzustellen?



Geschrieben von eulerscheZahl am 16.03.2016 um 16:47:

 

Ich sehe keins deiner 3 Probleme.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
static int[][] comb(int[] alphabet, int take) {
	int count = (int) Math.pow(alphabet.length, take);
	int[][] result = new int[count][];
	for (int i = 0; i < count; i++) {
		result[i] = new int[take];
		int n = i;
		for (int j = take - 1; j >= 0; j--) {
			result[i][j] = alphabet[n % alphabet.length];
			n /= alphabet.length;
		}
	}
	return result;
}


Forensoftware: Burning Board, entwickelt von WoltLab GmbH