Rekursion würfeltum/kombination

07.06.2016, 19:44

Nago

Rekursion würfeltum/kombination

Hi leute,
Ich hab schon die Suchfunktion genutzt, aber die sonstigen Topics zur Rekursion haben mir leider nicht weitergeholfen.

ich habe einen Turm, bestehend aus 4 Würfeln mit Farbigen Seiten (4 Farben, wie die auf den Würfeln auftachen wird vorgegeben). Und die Aufgabe alle durch rotation möglichen Turmstellungen zu finden, in denen nie zwei übereinander liegende Seitenflächen die gleiche farbe haben. Und dass ganze soll rekursiv geschehen. Meine einzigen erfahrungen mit rekursion bis jetzt sind standardbeispiele, wie fakultät/ggT und Türme von Hanoi. Aber bis jetzt haben die mir nciht wirklich weiter geholfen.

Ich habe bis jetzt versucht dass alles in einem Abwasch zu machen hab aber das Problem dass ich dann mit der Abbruchbedingung der Rekursion nicht klar komme:

Ich muss ja die Rotationen zählen um nicht ständig weiter zu Rotieren, da sich die Stellungen ja sonst wiederholen, hatte ich erstmal mit nem laufindex i gemacht. Dann hatte ich noch einen index j um fest zu legen welche Seite des Turms ich gerade betrachte. Allerdings kam mir jetzt während ich diesen post verfasse der Gedanke, dass ich anstatt einen index für die Seite zu nutzen, ja auch den gesamtem Turm rotieren könnte.....
Na und dann soll der algorithmus ja nicht bei einer Lösung abbrechen, sondern alle finden. Da kam mir dann der gedanke, dass mein Ansatz anscheinend einfach Falsch ist und ich dass irgendwie aufteilen muss. Aber da fällt mir jetzt kein Ansatz ein.

Habt ihr Tipps oder Hinweise zur Aufgabe oder zur generellen modellierung eines Rekusiven Algorithmus? Googlen bringt mir leider auch nur die oben erwähnten Standardbeispiele, die mir entweder nicht helfen weil sie zu einfach sind oder ich einen Zusammenhang übersehe.
Hänge jetzt schon seit gestern fest.

07.06.2016, 21:09

Auf diesen Beitrag antworten »

eulerscheZahl

Ich würde es so angehen:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:

Zähle(aktuellerWürfel, letzteFarbe) {
    wenn aktuellerWürfel außerhalb der verfügbaren Würfel: du bist fertig, also ist das Ergebnis 1.
    sonst:
        ergebnis = 0
        für jede würfelseite:
            wenn die Farbe gültig ist:
                ergebnis = ergebnis + Zähle(aktuellerWürfel+1, neueObersteFarbe)
        gib ergebnis zurück
}

Schau mal, wie weit du damit kommst. Wenn Fragen sind, einfach stellen. Es wäre dann aber hilfreich zu wissen, welche Programmiersprache du verwendest.

08.06.2016, 00:06

Auf diesen Beitrag antworten »

Nago

Ich danke dir für deine Hilfe,werde mich gleich (oder vllt eher morgen früh) damit auseinander setzen. Mit "verfügbarer Würfel" meinst du einfach die Würfel dies Turms die noch nciht geprüft wurden oder?

Hab leider festgestellt das ich die aufgabe erst falsch verstanden hatte: Gültige Stellungen sind alle, bei denen keine Farbe an einer Seite doppelt vorkommt, bzw, an denen jede Farbe 1 mal vorkommt (ist bei 4 farben und 4 Würfeln ja das selbe). Die formulierung "paarweise verschieden" hat mich glaub ich verwirrt.

Ich programmiere in java, und das gnaze soll objektorientiert sein.
Ich hab also eine Klasse Würfel, mit den Farben als Attributen und eine Klasse Turm, die als Attribut 4 Würfel hat. Natürlich noch ein paar andere Klassen. Das UML ist auch schon abgenommen, die Grundstruktur steht also fest.

08.06.2016, 06:18

Auf diesen Beitrag antworten »

eulerscheZahl

Ich wäre das etwa so angegangen:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

static Die[] dice = new Die[4]; //der Turm besteht aus 4 Würfeln
//TODO: Farben zuweisen, den Turm darfst du selbst reinwursteln

static void main(String[] args) {
	System.out.println(count(0, -1));
}

static int count(int currentDie, int lastColor) { //hier evtl noch den Turm übergeben, statt als static member
	if (currentDie == dice.length) return 1;
	//...
}

Du kannst natürlich auch einen Würfel statt des Index übergeben und dann auf null prüfen.

09.06.2016, 08:33

Auf diesen Beitrag antworten »

Nago

Ich danke dir nochmals für deine Hilfe.
Ich hatte ja versucht alles in einer Rekursiven funktion zu machen, habe mich jetzt aber entschieden, das ganze auf zu spalten. Eine methode, welche sämtliche würfelstellungen erzeugt und eine welche dann prüft welcher Turm als Lösung in Frage kommt. Die funktion für die Stellung sieht bis jetzt so aus:

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:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:

       //soll prüfen, ob der mitgegebene Turm eine gültige lösung ist(ist aber noch nicht fertig)
	public void pruefung(Turm turm, int n, int m){
		
		if ( n > 0 && m > 0)
			{
				if(turm.wuerfelListe[n].getFarbe()[m]!= turm.wuerfelListe[n-1].getFarbe()[m])
					{pruefung(turm, n - 1, m );
					}
				else {}
		}
		if (n == 0 && m > 0)
		  {	pruefung(turm, 3, m-1);}
		if (n == 0 && m == 0){
                       //hängt turm an lösungslist ran (ArrayList<Turm>)
			liste.addTurm(turm);}
		}
	public void stellungen(Turm turm, int seite, int hoehe, int vertikal){
		
		pruefung(turm, 3,3);
		
		if(seite>0 && vertikal > 0){
			
			turm.wuerfelListe[hoehe].vertikaleRotation1();
			stellungen(turm, seite ,hoehe, vertikal-1);}
			
		else if(seite > 0 && vertikal == 0){
			turm.wuerfelListe[hoehe].horizontaleRotation();
			 stellungen(turm, seite-1, hoehe, 4);}
			
		else if(seite == 0 && hoehe > 0 && vertikal == 0){
			 stellungen(turm, 4, hoehe-1, 4 );
			}
			
		else if (hoehe==0){
			System.out.println("huhu"); 
                       //gibt die lsite aus die die Türme enthält die gütlige lösungen sind
			liste.ausgabe();}
		}

Der macht aber noch nciht so wirklich was er soll. das "huhu" am ende is nur um die ausgabe zu testen, aber anscheinend wird hoehe nicht 0, was ich nicht verstehe. Ich sitze jetzt auch schon seit einigen tagen der Aufgabe und werde glaube ich langsam blind für den code.
Es Sei denn der Fehler liegt in der anderen Methode, an der arbeite ich gerade noch, schreib ich dann später vllt noch.

Ich hab halt auch schon wieder so viele variablen. Bin mir nicht sicher ob das so nötig ist, oder ob ichs mir einfach kompliziert mache.

09.06.2016, 08:52

Auf diesen Beitrag antworten »

eulerscheZahl

Wenn ich mir das anschauen soll, brauche ich auch deinen kompletten Code.
Du rufst da Funktionen auf, die nirgends definiert sind.

09.06.2016, 12:39

Auf diesen Beitrag antworten »

Nago

Sry, hab meinen code nochmal ergänzt.
Turm ist ein objekt mit attribut Würfel[ ] würfelliste, welches die 4 würfel des Turms enthält, mit den verschiedenen indizes wird gezählt welchen würfel, bzw. welche seite zum wie vielten mal wie gedreht oder vergleicht wird.Wie gesaagt, es sind schon wieder recht viele.

Das hat zwar nichts mehr mit rekursion zu tun, aber es gehört noch mit zur aufgabe und ich denke gerade darüber nach:

Die lösungsmenge sol keine rotationsinvarianten der Türme enthalten, aber ich ich keinen plan wie ich überprüfen soll, ob ein Turm schon gedreht enthalten ist.
Am anfang wurde mal contains() daher gesagt, aber das wird ja bei den Türmen nicht funktionieren, ich muss im Grunde ja die Farben im zusammenhang mit ihrer position verlgiechen. Es sei denn das geht klüger, aber da hab ich gar keine idee, wie man das bewerkstelligen soll.

09.06.2016, 16:57

Auf diesen Beitrag antworten »

eulerscheZahl

Mir ist die Aufgabe leider immer noch nicht komplett klar. Und das Fehlen der Initialisierung im deinem Codeausschnitt macht das nicht besser.

Sind die Würfel gleich? Wenn verschieden, ist dann die Reihenfolge vertauschbar?
Was verstehst du unter rotationsinvariant?
Sind zwei Türme gleich, wenn man einen auf den Kopf stellt und dann den anderen erhält?
Kommt es nur auf die Boden- und Deckfläche an, oder auch auf Front und Seite?

12.06.2016, 15:21

Auf diesen Beitrag antworten »

Nago

Die Würfel können, müssen aber nciht gleich sein. Wie die aussehen wird über eine Eingabe festgelegt.
Es gibt 4 Farben, ein Würfel kann alle farben haben, aber er kann zum Beispiel auch komplett blau sein.

Mit Rotationsinvariante ist gemeint, dass ein Turm, der nur durch drehung eines vorhanden Turms entsteht, als der Selbe angesehen wird, also er nicht nochmal in die Lösungsmenge kommt.

Die Würfel ändern ihre höhe nicht, der Würfel der zum Beispiel ganz unten steht, bleibt auhc unten. (Der unterste Würfel wird übrigens nicht rotiert).

Zitat:

Sind zwei Türme gleich, wenn man einen auf den Kopf stellt und dann den anderen erhält?

Nein. Es sei denn natürlich die Farben wären Symmetrisch. Aber dann ist der Turm ja eh keine Lösung.

Zitat:

Kommt es nur auf die Boden- und Deckfläche an, oder auch auf Front und Seite?

Für eine gültige Lösung kommt es nur auf die Seitenflächen an. Jede der 4 Seiten eines Turmes muss also jede Farbe einmal enthalten. Ob die Turmseiten gleich sind ist egal.
Die Boden und Deckel-flächen kommen erst ins spiel, wenn ein Würfel vertikal gedreht wird, weil sie ja dann zu Seitenflächen werden.

Der Ansatz oben wird wahrscheinlich wieder verworfen. Ich fang nochmal neu an, weil es irgendwie nicht alles ausgibt (das was oben steht ist auch nicht mehr 100%ig aktuell).
Und ich weiß leider nicht ob ich nah dran oder ewig weit weg bin.

Der Farbvergleich wird jetzt vermutlich einfach iterativ stattfinden. Es geht um grunde einfach nur noch um die verschiedenen Turmstellungen.

Ich hoffe ich habe etwas klarheit reingebracht. Musste neulich selber nochmal in der Uni nachfragen, weil mir plötzlich auch nich alles klar war.

Hier nochmal der aktuellste code der stellungen methode:

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:

	public void stellungen(Turm turm, int a, int b, int c, int d){
	/**	
		if(pruefung(turm))
			{liste.addTurm(turm);}
		
		if( vertikal > 0 && hoehe > 0){
			
			turm.wuerfelListe[hoehe].vertikaleRotation1();
			if(pruefung(turm))
				{liste.addTurm(turm);}
			horizontaleRotation();
			stellungen(turm, seite ,hoehe, vertikal-1);}
			
	    if(seite > 0 && vertikal == 0 && hoehe > 0){
			turm.wuerfelListe[hoehe].horizontaleRotation();
			 stellungen(turm, seite-1, hoehe, 3);}
			
	    if(seite == 0 && hoehe > 1 && vertikal == 0){
			 stellungen(turm, 3, hoehe-1, 3 );}
			
		if (seite == 0 && hoehe == 1 && vertikal == 0) {
			System.out.println("huhu");
			liste.ausgabe();
			}

Die mehtode wird mit stellungen(turm, 0,0,0,0); aufgerufen.

12.06.2016, 17:14

Auf diesen Beitrag antworten »

eulerscheZahl

Hier mal nur der Algorithmus (ohne objektorientierte Programmierung). Der Testfall ist zufällig. Es kann also ein paar Versuche dauern, bis du eine Lösung findest.

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:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:

import java.util.HashSet;
import java.util.Random;

public class Main {
	public static void main(String[] args) {

		int[][] die = new int[4][6];
		Random random = new Random();
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 6; j++)
				die[i][j] = random.nextInt(4);
		}

		System.out.println(countStates(die, 0, new int[4][4]));
	}

	static HashSet<Long> towers = new HashSet<Long>();

	/**
	 * count number of ways to build a tower
	 * 
	 * @param die
	 *            the die to use
	 *            index0: index of the die
	 *            index1: color at face - two opposite faces have a difference
	 *            of 3 in the index
	 * @param index
	 *            next die to use
	 * @param colors
	 *            the colors used at the sides
	 *            index0: height
	 *            index1: front, back, right, left
	 * @return
	 */
	private static int countStates(int[][] die, int index, int[][] colors) {
		if (index == 4) {
			//check for duplicates
			long[] values = new long[4]; //represent the towers by longs, fits in 64 bit
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					for (int k = 0; k < 4; k++) {
						values[i] *= 4;
						values[i] += colors[j][k];
					}
				}
			}
			boolean dublicate = false;
			for (int i = 0; i < 4; i++) {
				if (towers.contains(values[i]))
					dublicate = true;
			}
			if (!dublicate) {
				towers.add(values[0]);
				String[] text = new String[] { "front", "left", "back", "right" };
				for (int face = 0; face < 4; face++) {
					System.out.print(text[face] + ": ");
					for (int height = 0; height < 4; height++)
						System.out.print(colors[height][face]);
					System.out.print("\t");
				}
				System.out.println();
				return 1;
			}
			return 0;
		}
		int result = 0;
		for (int topColor = 0; topColor < 6; topColor++) {
			colors[index][0] = die[index][(topColor + 1) % 6];
			colors[index][1] = die[index][(topColor + 2) % 6];
			colors[index][2] = die[index][(topColor + 4) % 6];
			colors[index][3] = die[index][(topColor + 5) % 6];
			if (valid(colors, index))
				result += countStates(die, index + 1, colors);
			colors[index][1] = die[index][(topColor + 5) % 6];
			colors[index][3] = die[index][(topColor + 2) % 6];
			if (valid(colors, index))
				result += countStates(die, index + 1, colors);
		}
		return result;
	}

	static boolean valid(int[][] colors, int index) {
		for (int face = 0; face < 4; face++) {
			boolean[] used = new boolean[4];
			for (int height = 0; height <= index; height++) {
				if (used[colors[height][face]])
					return false;
				used[colors[height][face]] = true;
			}
		}
		return true;
	}
}

15.06.2016, 02:20

Auf diesen Beitrag antworten »

Nago

Erstmal vielen dank für deine Hilfe. Habs jetzt fast geschaft. Das einzige was noch ernste probleme bereitet is der Filter bezüglichd er Rotationsinvarianten. Es fällt mir ein wenig schwer deinen algorithmus um zu setzen, weil es sich ja bei mir um objekte handelt(enums, Würfel, Türme), vor allem aber weil ich teilweise ncihtmal versteht wie es funktioniert:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

		if (index == 4) {
			//check for duplicates
			long[] values = new long[4]; //represent the towers by longs, fits in 64 bit
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					for (int k = 0; k < 4; k++) {
						values[i] *= 4;
						values[i] += colors[j][k];
					}
				}
			}

Schätze ich steht einfach auf dem schlacuh, aber wozu die multiplikation/addition bei values[i]?

15.06.2016, 07:26

Auf diesen Beitrag antworten »

eulerscheZahl

In colors stehen Werte in [0;3]. Man kann die Werte also einen nach dem anderen in eine Zahl mit Basis 4 schreiben, ohne Platz zu verschenken. So komprimiere ich alle Seitenflächen des Turms in ein einziges long. Auf die Weise kann ich bei anderen Türmen leicht prüfen, ob ich sie schon hatte.
Je nach Seitenfläche, mit der ich starte, kann das aber eine andere Zahl geben. Deshalb starte ich mit allen vier Seitenflächen und prüfe für jede, ob ich sie schon hatte.

Für dich gilt: du musst ja prüfen, ob du einen Turm schon hattest. Dazu könntest du jeden Turm mit jedem anderen vergleichen. Je mehr Türme, desto länger dauert das.
Alternativ kannst du das Comparable Interface implementieren und hashCode überschreiben. Dabei muss der Wert des Hashcodes rotationsinvariant sein.

Neue Frage »

Antworten »

Rekursion würfeltum/kombination

Verwandte Themen