Johnson and Trotter algorithm in Java umsetzen

Java-Forum Allgemeine Themen
1

Hallo Comm.,
ich versuche gerade, den Johnson and Trotter algorithm in Java umzusetzen (alle Permutationen (iterativ) berechnen), aber scheitere kläglich… Könnt ihr mir sagen, was daran falsch ist - oder wenigstens, was daran richtig wäre?

	public static void JohnsonAndTrotterAlgorithm(int[] a) {
		boolean[] direction = new boolean[a.length];
		boolean[] mobile = new boolean[a.length];

		for (int j = 0; j < 20; j++) {
			int max = getLargestMobileIndex(a, mobile);
			if (!direction[max]) {
				if (max - 1 < 0) {
					mobile[max] = !mobile[max];
				} else if (a[max] > a[max - 1]) {
					int t = a[max];
					a[max] = a[max - 1];
					a[max - 1] = t;
					System.out.println(Arrays.toString(a));
				} else {
					direction[max] = !direction[max];
				}
			} else {
				if (max + 1 == a.length) {
					mobile[max] = !mobile[max];
				} else if (a[max] > a[max + 1]) {
					int t = a[max];
					a[max] = a[max + 1];
					a[max + 1] = t;
					System.out.println(Arrays.toString(a));
				} else {
					direction[max] = !direction[max];
				}
			}

		}
	}

	public static int getLargestMobileIndex(int[] a, boolean[] mobile) {
		int maxIndex = 0;
		for (int i = 0; i < a.length; i++) {
			if (!mobile[i]) {
				maxIndex = i;
				break;
			}
		}
		for (int i = 0; i < a.length; i++) {
			if (!mobile[i] && a[i] > a[maxIndex]) {
				maxIndex = i;
			}
		}
		return maxIndex;
	}

	public static void main(String[] args) {
		JohnsonAndTrotterAlgorithm(new int[] { 1, 2, 3, 4, 5 });
	}

Ich weiß nicht genau,

  • wann ein Index nicht mehr mobil ist,
  • wann ein Richtungswechsel erfolgt,
  • welcher Index in einer Iteration vertauscht wird,
  • wie lange das Ganze/(j) läuft,
  • etc.

Schonmal vielen Dank & schönen Abend

2

Vergleiche doch erst mal deine Implementierung mit anderen, z.B. https://rosettacode.org/wiki/Permutations_by_swapping

3

Moin,
ich habe mir den C++ Code angeschaut, und diesen übernommen, aber dabei wird ein „Zwischenarray“ verwendet, welches ich hierbei nicht habe:

	public static void JohnsonAndTrotterAlgorithm(int[] a) {
		final int n = a.length;
		boolean[] direction = new boolean[n];
		// Arrays.fill(direction, true);
		for (int j = 0; j < 40; j++) {
			int max = getLargestMobileIndex(a, direction);
			if (max != -1) {
				int d = direction[max] ? -1 : +1;
				int max2 = max + d;

				swap(a, max, max2);
				for (int i = max + 1; i < n; i++) {
					direction[i] = !direction[i];
				}
			} else {
				if (!direction[0]) {
					swap(a, 0, 1);
				} else {
					swap(a, n - 1, n - 2);
					for (int i = n - 1; i < n; i++) {
						direction[i] = !direction[i];
					}
				}

			}

			System.out.println(Arrays.toString(a));
		}
	}

	public static int getLargestMobileIndex(int[] a, boolean[] direction) {
		for (int i = a.length - 1; i >= 0; i--) {
			int d = direction[i] ? -1 : +1;
			if (i + d >= 0 && i + d < a.length && a[i] > a[i + d]) {
				return i;
			}
		}
		return -1;
	}

Die Ausgabe für 1,2,3,4 ist noch falsch:

[2, 1, 3, 4]
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 4, 2, 3]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 1, 2, 3]
[1, 4, 2, 3]
[1, 4, 3, 2]
[1, 3, 4, 2]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 3, 2, 4]
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 4, 2, 3]
[1, 2, 4, 3]
[1, 2, 3, 4]
[2, 1, 3, 4]
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 4, 2, 3]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 1, 2, 3]
[1, 4, 2, 3]
[1, 4, 3, 2]
[1, 3, 4, 2]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 3, 2, 4]
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 4, 2, 3]
[1, 2, 4, 3]
[1, 2, 3, 4]
...
4

Nimm doch einfach die Java Implementierung:

https://rosettacode.org/wiki/Permutations_by_swapping#Java

Iterativ und Rekursiv beides vorhanden. Da kann man ja sehen, wo das Problem ist.

5

Die iterative Variante ist meines Erachtens nicht Johnson and Trotter…

6

Dann wirst du ums debuggen nicht herum kommen.