Permutationen eines Arrays in Java

1. Einleitung

In diesem Artikel erfahren Sie, wie Sie Permutationen eines Arrays erstellen.

Zuerst definieren wir, was eine Permutation ist. Zweitens werden wir uns einige Einschränkungen ansehen. Und drittens betrachten wir drei Möglichkeiten, um sie zu berechnen: rekursiv, iterativ und zufällig.

Wir werden uns auf die Implementierung in Java konzentrieren und daher nicht auf viele mathematische Details eingehen.

2. Was ist eine Permutation?

Eine Permutation einer Menge ist eine Neuordnung ihrer Elemente. Eine Menge, die aus n Elementen besteht, hat n! Permutationen. Hier n! ist die Fakultät, die das Produkt aller positiven ganzen Zahlen ist, die kleiner oder gleich n sind .

2.1. Beispiel

Das Array von ganzen Zahlen [3,4,7] hat drei Elemente und sechs Permutationen:

n! = 3! = 1 x 2 x 3 = 6

Permutationen: [3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]

2.2. Einschränkungen

Die Anzahl der Permutationen steigt mit n schnell an . Während es nur wenige Sekunden dauert, um alle Permutationen von zehn Elementen zu generieren, dauert es zwei Wochen, um alle Permutationen von 15 Elementen zu generieren:

3. Algorithmen

3.1. Rekursiver Algorithmus

Der erste Algorithmus, den wir betrachten, ist der Heap-Algorithmus. Es ist ein rekursiver Algorithmus, der alle Permutationen erzeugt, indem ein Element pro Iteration ausgetauscht wird.

Das Eingabearray wird geändert. Wenn wir das nicht wollen, müssen wir eine Kopie des Arrays erstellen, bevor wir die Methode aufrufen:

public static  void printAllRecursive( int n, T[] elements, char delimiter) { if(n == 1) { printArray(elements, delimiter); } else { for(int i = 0; i < n-1; i++) { printAllRecursive(n - 1, elements, delimiter); if(n % 2 == 0) { swap(elements, i, n-1); } else { swap(elements, 0, n-1); } } printAllRecursive(n - 1, elements, delimiter); } } 

Die Methode verwendet zwei Hilfsmethoden:

private void swap(T[] input, int a, int b) { T tmp = input[a]; input[a] = input[b]; input[b] = tmp; }
private void printArray(T[] input) { System.out.print('\n'); for(int i = 0; i < input.length; i++) { System.out.print(input[i]); } } 

Hier schreiben wir das Ergebnis in System.out , können das Ergebnis jedoch einfach in einem Array oder in einer Liste speichern.

3.2. Iterativer Algorithmus

Der Heap-Algorithmus kann auch mithilfe von Iterationen implementiert werden:

int[] indexes = new int[n]; int[] indexes = new int[n]; for (int i = 0; i < n; i++) { indexes[i] = 0; } printArray(elements, delimiter); int i = 0; while (i < n) { if (indexes[i] < i) { swap(elements, i % 2 == 0 ? 0: indexes[i], i); printArray(elements, delimiter); indexes[i]++; i = 0; } else { indexes[i] = 0; i++; } } 

3.3. Permutationen in lexikographischer Reihenfolge

Wenn die Elemente vergleichbar sind, können wir Permutationen erzeugen, die nach der natürlichen Reihenfolge der Elemente sortiert sind:

public static 
    
      void printAllOrdered( T[] elements, char delimiter) { Arrays.sort(elements); boolean hasNext = true; while(hasNext) { printArray(elements, delimiter); int k = 0, l = 0; hasNext = false; for (int i = elements.length - 1; i > 0; i--) { if (elements[i].compareTo(elements[i - 1]) > 0) { k = i - 1; hasNext = true; break; } } for (int i = elements.length - 1; i > k; i--) { if (elements[i].compareTo(elements[k]) > 0) { l = i; break; } } swap(elements, k, l); Collections.reverse(Arrays.asList(elements).subList(k + 1, elements.length)); } } 
    

Dieser Algorithmus hat in jeder Iteration eine umgekehrte Operation und ist daher auf Arrays weniger effizient als der Heap-Algorithmus.

3.4. Randomisierter Algorithmus

Wenn n groß ist, können wir eine zufällige Permutation erzeugen, indem wir das Array mischen:

Collections.shuffle(Arrays.asList(elements));

Wir können dies mehrmals tun, um eine Stichprobe von Permutationen zu erzeugen.

Wir können dieselben Permutationen mehr als einmal erstellen, aber für große Werte von n sind die Chancen, dieselbe Permutation zweimal zu generieren, gering.

4. Fazit

Es gibt viele Möglichkeiten, alle Permutationen eines Arrays zu generieren. In diesem Artikel haben wir den rekursiven und iterativen Heap-Algorithmus und das Generieren einer sortierten Liste von Permutationen gesehen.

Es ist nicht möglich, alle Permutationen für große Arrays zu generieren. Daher können wir stattdessen zufällige Permutationen generieren.

Die Implementierung aller Codefragmente in diesem Artikel finden Sie in unserem Github-Repository.