Wie kann ich alle Permutationen eines Arrays generieren?

Erzeugen von Permutationen eines Arrays

Die Permutation eines Arrays umfasst eine einzigartige Anordnung seiner Elemente. Für ein N-Element-Array gibt es N! (N-faktorielle) unterschiedliche Permutationen. Ziel dieser Frage ist es, einen Algorithmus zum Generieren dieser Permutationen zu skizzieren.

Algorithmus:

Berücksichtigen Sie die folgenden Schritte zum Generieren von Array-Permutationen:

1. Initialisieren: Beginnen Sie damit, das erste Element als Drehpunkt zu nehmen und es an der ersten Position des Stroms zu platzieren Permutationsliste.

2. Rekursive Permutation: Schleife durch die verbleibenden Elemente des Arrays. Tauschen Sie jedes Element mit dem Pivot aus, rufen Sie die Permutationsfunktion rekursiv mit dem aktualisierten Pivot an der nächsten Position auf und tauschen Sie erneut, um die ursprüngliche Reihenfolge wiederherzustellen.

   • Beispielsweise gegeben {3,4,6, 2,1} mit Pivot 3 iterieren Sie über {4,6,2,1}. Sie tauschen 4 mit 3, permutieren rekursiv {4, 3, 2, 1} mit Pivot 4 und tauschen zurück.
3. Beendigung: Wenn die Schleife erreicht Letztes Element, die aktuelle Permutationsliste ist vollständig. Geben Sie es aus.

Implementierung:

Hier ist eine Python-Implementierung des obigen Algorithmus:

def generate_permutations(arr):
  perms = []
  _generate_permutations_helper(arr, 0, perms)
  return perms


def _generate_permutations_helper(arr, start, perms):
  if start == len(arr) - 1:
    perms.append(arr.copy())
  else:
    for i in range(start, len(arr)):
      arr[start], arr[i] = arr[i], arr[start]
      _generate_permutations_helper(arr, start + 1, perms)
      arr[start], arr[i] = arr[i], arr[start]

Beispiel Verwendung:

arr = [3, 4, 6, 2, 1]
permutations = generate_permutations(arr)
print(permutations)  # [[3, 4, 6, 2, 1], [3, 4, 2, 6, 1], ... ]

Hinweis: Diese Methode kann für die Speichernutzung optimiert werden, indem nur die Start- und Endelemente der aktuellen Permutationen beibehalten werden und die vollständige Liste erst am erstellt wird Ende, wodurch die Notwendigkeit entfällt, die gesamte Liste der Permutationen im Speicher zu behalten.

Das obige ist der detaillierte Inhalt vonWie kann ich alle Permutationen eines Arrays generieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!