Kombinatorik mit Rekursion

11.03.2016, 12:41

Haevelin

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

11.03.2016, 14:05

Auf diesen Beitrag antworten »

Haevelin

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;}
 		 		 	}

11.03.2016, 14:19

Auf diesen Beitrag antworten »

eulerscheZahl

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);
		}
	}
}

15.03.2016, 16:41

Auf diesen Beitrag antworten »

Haevelin

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.

15.03.2016, 17:13

Auf diesen Beitrag antworten »

eulerscheZahl

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

16.03.2016, 15:51

Auf diesen Beitrag antworten »

Haevelin

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?

16.03.2016, 16:47

Auf diesen Beitrag antworten »

eulerscheZahl

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;
}

Neue Frage »

Antworten »

Kombinatorik mit Rekursion

Verwandte Themen