Türme von Hanoi, Suchbaum aufstellen funktioniert nicht

Schaut euch mal die grafische Repräsentation auf Wikipedia an: https://en.wikipedia.org/wiki/Tower_of_Hanoi#Graphical_representation

So einen Suchbaum für beliebige n möchte ich mit Graphviz programmatisch auch aufstellen… Bei mir fehlen für n=2 aber ein paar Knoten:

graph G {
aa -- ab
ab -- bc
bc -- ac
ac -- cc
ac -- ab
ab -- bb
bb -- bc
bc -- ac
}

Hättet ihr eine Idee, woran das liegen könnte?

	public static class Towers {
		public ArrayList<Integer> a, b, c;

		public Towers(int n) {
			a = new ArrayList<>();
			b = new ArrayList<>();
			c = new ArrayList<>();
			for (int i = n; i > 0; i--) {
				a.add(i);
			}
		}

		public Towers(Towers o, ArrayList<Integer> x, ArrayList<Integer> y) {
			y.add(x.remove(x.size() - 1));
			a = new ArrayList<>(o.a);
			b = new ArrayList<>(o.b);
			c = new ArrayList<>(o.c);
			x.add(y.remove(y.size() - 1));
		}

		@Override
		public int hashCode() {
			return Objects.hash(a, b, c);
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Towers other = (Towers) obj;
			return Objects.equals(a, other.a) && Objects.equals(b, other.b) && Objects.equals(c, other.c);
		}
	}

	public static String graph(int n) {
		StringBuilder b = new StringBuilder();
		b.append("graph G {\n");
		Towers t = new Towers(n);
		Set<Towers> s = new HashSet<>();
		s.add(t);
		b.append(graph(t, s));
		b.append("}");
		return b.toString();
	}

	public static String graph(Towers t, Set<Towers> s) {
		StringBuilder b = new StringBuilder();
		if (!t.a.isEmpty()) {
			if (last(t.a) < last(t.b)) {
				Towers t2 = new Towers(t, t.a, t.b);
				if (!s.contains(t2)) {
					s.add(t2);
					b.append(edge(t, t2));
					b.append(graph(t2, s));
				}
			}
			if (last(t.a) < last(t.c)) {
				Towers t2 = new Towers(t, t.a, t.c);
				if (!s.contains(t2)) {
					s.add(t2);
					b.append(edge(t, t2));
					b.append(graph(t2, s));
				}
			}
		}
		if (!t.b.isEmpty()) {
			if (last(t.b) < last(t.a)) {
				Towers t2 = new Towers(t, t.b, t.a);
				if (!s.contains(t2)) {
					s.add(t2);
					b.append(edge(t, t2));
					b.append(graph(t2, s));
				}
			}
			if (last(t.b) < last(t.c)) {
				Towers t2 = new Towers(t, t.b, t.c);
				if (!s.contains(t2)) {
					s.add(t2);
					b.append(edge(t, t2));
					b.append(graph(t2, s));
				}
			}
		}
		if (!t.c.isEmpty()) {
			if (last(t.c) < last(t.a)) {
				Towers t2 = new Towers(t, t.c, t.a);
				if (!s.contains(t2)) {
					s.add(t2);
					b.append(edge(t, t2));
					b.append(graph(t2, s));
				}
			}
			if (last(t.c) < last(t.b)) {
				Towers t2 = new Towers(t, t.c, t.b);
				if (!s.contains(t2)) {
					s.add(t2);
					b.append(edge(t, t2));
					b.append(graph(t2, s));
				}
			}
		}
		return b.toString();
	}

	public static String edge(Towers t1, Towers t2) {
		StringBuilder b = new StringBuilder();
		for (int j = 0; j < t1.a.size(); j++) {
			b.append('a');
		}
		for (int j = 0; j < t1.b.size(); j++) {
			b.append('b');
		}
		for (int j = 0; j < t1.c.size(); j++) {
			b.append('c');
		}
		b.append(" -- ");
		for (int j = 0; j < t2.a.size(); j++) {
			b.append('a');
		}
		for (int j = 0; j < t2.b.size(); j++) {
			b.append('b');
		}
		for (int j = 0; j < t2.c.size(); j++) {
			b.append('c');
		}
		b.append("\n");
		return b.toString();
	}

	public static int last(List<Integer> l) {
		if (l.isEmpty())
			return 100;
		return l.get(l.size() - 1);
	}

	public static void main(String[] args) {
		System.out.println(graph(2));
	}

Die edge-Methode ist falsch… die haben eine ganz seltsame Notation bei Wikipedia… zuerst werden die Säulen absteigend nach dem Wert der jeweils obersten Scheibe sortiert, dann wird von l. nach r. für jede Säule Anzahl der Scheiben-mal der Buchstabe der Säule wiederholt. :eyes:

Ich hab jetzt so etwas, wobei aber noch irgendwo ein Fehler ist… Ich muss den ganzen Haufen noch mal umschmeißen:

	public static String edge(Towers t1, Towers t2) {
		StringBuilder b = new StringBuilder();
		Towers t = t1;
		if (t.last(0).orElse(0) > t.last(1).orElse(100)) {
			if (t.last(0).orElse(0) > t.last(2).orElse(100)) {
				if (t.last(1).orElse(0) > t.last(2).orElse(100)) {
					// a>b, a>c, b>c = a>b>c
					for (int i = 0; i < t.size(0); i++) {
						b.append('a');
					}
					for (int i = 0; i < t.size(1); i++) {
						b.append('b');
					}
					for (int i = 0; i < t.size(2); i++) {
						b.append('c');
					}
				} else {
					// a>b, a>c, c>b = a>c>b
					for (int i = 0; i < t.size(0); i++) {
						b.append('a');
					}
					for (int i = 0; i < t.size(2); i++) {
						b.append('c');
					}
					for (int i = 0; i < t.size(1); i++) {
						b.append('b');
					}
				}
			} else {
				// a>b, c>a = c>a>b
				for (int i = 0; i < t.size(2); i++) {
					b.append('c');
				}
				for (int i = 0; i < t.size(0); i++) {
					b.append('a');
				}
				for (int i = 0; i < t.size(1); i++) {
					b.append('b');
				}
			}
		} else {
			if (t.last(0).orElse(0) > t.last(2).orElse(100)) {
				if (t.last(1).orElse(0) > t.last(2).orElse(100)) {
					// b>a, a>c, b>c = b>a>c
					for (int i = 0; i < t.size(1); i++) {
						b.append('b');
					}
					for (int i = 0; i < t.size(0); i++) {
						b.append('a');
					}
					for (int i = 0; i < t.size(2); i++) {
						b.append('c');
					}
				}
			} else {
				if (t.last(1).orElse(0) > t.last(2).orElse(100)) {
					// b>a, c>a, b>c = b>c>a
					for (int i = 0; i < t.size(1); i++) {
						b.append('b');
					}
					for (int i = 0; i < t.size(2); i++) {
						b.append('c');
					}
					for (int i = 0; i < t.size(0); i++) {
						b.append('a');
					}
				} else {
					// b>a, c>a, c>b = c>b>a
					for (int i = 0; i < t.size(2); i++) {
						b.append('c');
					}
					for (int i = 0; i < t.size(1); i++) {
						b.append('b');
					}
					for (int i = 0; i < t.size(0); i++) {
						b.append('a');
					}
				}
			}
		}
		b.append(" -- ");
		t = t2;
		if (t.last(0).orElse(0) > t.last(1).orElse(100)) {
			if (t.last(0).orElse(0) > t.last(2).orElse(100)) {
				if (t.last(1).orElse(0) > t.last(2).orElse(100)) {
					// a>b, a>c, b>c = a>b>c
					for (int i = 0; i < t.size(0); i++) {
						b.append('a');
					}
					for (int i = 0; i < t.size(1); i++) {
						b.append('b');
					}
					for (int i = 0; i < t.size(2); i++) {
						b.append('c');
					}
				} else {
					// a>b, a>c, c>b = a>c>b
					for (int i = 0; i < t.size(0); i++) {
						b.append('a');
					}
					for (int i = 0; i < t.size(2); i++) {
						b.append('c');
					}
					for (int i = 0; i < t.size(1); i++) {
						b.append('b');
					}
				}
			} else {
				// a>b, c>a = c>a>b
				for (int i = 0; i < t.size(2); i++) {
					b.append('c');
				}
				for (int i = 0; i < t.size(0); i++) {
					b.append('a');
				}
				for (int i = 0; i < t.size(1); i++) {
					b.append('b');
				}
			}
		} else {
			if (t.last(0).orElse(0) > t.last(2).orElse(100)) {
				if (t.last(1).orElse(0) > t.last(2).orElse(100)) {
					// b>a, a>c, b>c = b>a>c
					for (int i = 0; i < t.size(1); i++) {
						b.append('b');
					}
					for (int i = 0; i < t.size(0); i++) {
						b.append('a');
					}
					for (int i = 0; i < t.size(2); i++) {
						b.append('c');
					}
				}
			} else {
				if (t.last(1).orElse(0) > t.last(2).orElse(100)) {
					// b>a, c>a, b>c = b>c>a
					for (int i = 0; i < t.size(1); i++) {
						b.append('b');
					}
					for (int i = 0; i < t.size(2); i++) {
						b.append('c');
					}
					for (int i = 0; i < t.size(0); i++) {
						b.append('a');
					}
				} else {
					// b>a, c>a, c>b = c>b>a
					for (int i = 0; i < t.size(2); i++) {
						b.append('c');
					}
					for (int i = 0; i < t.size(1); i++) {
						b.append('b');
					}
					for (int i = 0; i < t.size(0); i++) {
						b.append('a');
					}
				}
			}
		}
		b.append("\n");
		return b.toString();
	}

Hab es hinbekommen:

graph G {
aa -- ba
ba -- bc
bc -- ac
ac -- cc
cc -- bc
ac -- ab
ab -- bb
bb -- cb
cb -- ca
ca -- aa
ca -- ba
cb -- ab
}

Wie man jetzt Graphviz dot dazu hinbringen könnte, dass es genau so wie bei Wikipedia aussieht, das wüsstet ihr nicht oder?

Also, ich hab es jetzt hinbekommen, aber noch nicht das mit Graphviz dot…

Aber mir ist noch etwas anderes aufgefallen… Die auf Wikipedia verwendete Notation ist nur für 1<=n<=3 oder n<=4 eindeutig… Darüber hinaus werden nicht gleiche „Spielzustände“ in einem Knoten zusammengefasst, wie man hieran erkennen kann:

Zusammenfassung
	public static class Towers {
		public static class Tower implements Comparable<Tower> {
			public List<Integer> discs = new ArrayList<>();
			public char chr;

			public Tower(int n, char c) {
				for (int i = n; i > 0; i--) {
					discs.add(i);
				}
				chr = c;
			}

			public Tower(Tower o) {
				discs.addAll(o.discs);
				chr = o.chr;
			}

			public Optional<Integer> last() {
				if (discs.isEmpty())
					return Optional.empty();
				return Optional.of(discs.get(discs.size() - 1));
			}

			public Optional<Integer> size() {
				return Optional.of(discs.size());
			}

			public int pop() {
				return discs.remove(discs.size() - 1);
			}

			public void push(int i) {
				discs.add(i);
			}

			public char chr() {
				return chr;
			}

			/**
			 * ascending, last disc = top disc
			 */
			@Override
			public int compareTo(Main.Towers.Tower o) {
				return last().orElse(0).compareTo(o.last().orElse(0));
			}
		}

		public List<Tower> ts = new ArrayList<>();
		public String edge;

		public Towers(int n) {
			ts.add(new Tower(n, 'a'));
			ts.add(new Tower(0, 'b'));
			ts.add(new Tower(0, 'c'));
			edge = computeEdge();
		}

		public Towers(Towers o, int a, int b) {
			for (int i = 0; i < 3; i++) {
				ts.add(new Tower(o.ts.get(i)));
			}
			ts.get(b).push(ts.get(a).pop());
			edge = computeEdge();
		}

		public List<Tower> computeSortedTowers() {
			List<Tower> t = new ArrayList<>();
			for (int i = 0; i < 3; i++) {
				t.add(new Tower(ts.get(i)));
			}
			Collections.sort(t);
			return t;
		}

		public final String computeEdge() {
			StringBuilder builder = new StringBuilder();
			List<Tower> sortedTowers = computeSortedTowers();
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < sortedTowers.get(i).size().orElse(0); j++) {
					builder.append(sortedTowers.get(i).chr());
				}
			}
			return builder.toString();
		}

		public String edge() {
			return edge;
		}

		public Optional<Integer> last(int a) {
			return ts.get(a).last();
		}

		@Override
		public int hashCode() {
			return Objects.hash(edge);
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Towers other = (Towers) obj;
			return Objects.equals(edge, other.edge);
		}
	}

	public static class Edge {
		public Towers a, b;

		public Edge(Towers t1, Towers t2) {
			a = t1;
			b = t2;
		}

		@Override
		public int hashCode() {
			return Objects.hash(a, b);
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Edge other = (Edge) obj;
			return Objects.equals(a, other.a) && Objects.equals(b, other.b);
		}
	}

	public static String graph(int n) {
		StringBuilder b = new StringBuilder();
		b.append("graph G {\n");
		Towers towers = new Towers(n);
		Set<Edge> edges = new HashSet<>();
		b.append(graph(towers, edges));
		b.append("}");
		return b.toString();
	}

	private static String graph(Towers towers, Set<Edge> edges) {
		StringBuilder builder = new StringBuilder();
		for (int a = 0; a < 3; a++) {
			for (int b = 0; b < 3; b++) {
				if (a != b) {
					if (towers.last(a).orElse(100) < towers.last(b).orElse(100)) {
						Towers t2 = new Towers(towers, a, b);
						Edge e2 = new Edge(towers, t2);
						if (!edges.contains(e2)) {
							edges.add(e2);
							edges.add(new Edge(t2, towers));
							builder.append(edge(towers, t2));
							builder.append(graph(t2, edges));
						}
					}
				}
			}
		}
		return builder.toString();
	}

	private static String edge(Towers t1, Towers t2) {
		StringBuilder builder = new StringBuilder();
		builder.append(t1.edge());
		builder.append(" -- ");
		builder.append(t2.edge());
		builder.append("\n");
		return builder.toString();
	}

	public static void main(String[] args) {
		System.out.println(graph(1).split("\n").length);
		System.out.println(graph(2).split("\n").length);
		System.out.println(graph(3).split("\n").length);
		System.out.println(graph(4).split("\n").length);
		System.out.println(graph(5).split("\n").length);
		System.out.println(graph(6).split("\n").length);
	}

Hättet ihr noch eine Idee?