Rekursive Array-Permutationen in JavaScript

Einführung

In diesem Lab werden wir das Konzept von Array-Permutationen in JavaScript erkunden. Wir werden lernen, wie man Rekursion verwendet, um alle möglichen Permutationen der Elemente eines Arrays zu generieren, auch wenn sie Duplikate enthalten. Wir werden auch verstehen, wie man Array-Methoden wie map() und reduce() verwendet, um die verschiedenen Permutationen zu einem einzelnen Array zu kombinieren. Denken wir jedoch daran, dass das Ausführen dieser Funktion auf Arrays mit mehr als 8 bis 10 Elementen die Ausführungszeit erheblich erhöhen und den Browser zum Abstürzen bringen kann.

Skills Graph

Wie man alle Array-Permutationen generiert

Um mit der Programmierung zu üben, öffnen Sie das Terminal/SSH und geben Sie node ein.

Hier ist ein Algorithmus, der alle Permutationen der Elemente eines Arrays generiert (auch wenn es Duplikate enthält). Folgen Sie diesen Schritten, um ihn zu implementieren:

1. Verwenden Sie Rekursion.
2. Für jedes Element im gegebenen Array erstellen Sie alle partiellen Permutationen für die restlichen Elemente.
3. Verwenden Sie Array.prototype.map(), um das Element mit jeder partiellen Permutation zu kombinieren, und dann Array.prototype.reduce(), um alle Permutationen in einem Array zu kombinieren.
4. Die Basisfälle sind für Arrays mit einer Länge von 2 oder 1.
5. Achten Sie darauf, dass die Ausführungszeit dieser Funktion exponentiell mit jedem Array-Element zunimmt. Mehr als 8 bis 10 Einträge können dazu führen, dass Ihr Browser hängt, wenn er versucht, alle verschiedenen Kombinationen zu lösen.

Hier ist der Code:

const permutations = (arr) => {
  if (arr.length <= 2) return arr.length === 2 ? [arr, [arr[1], arr[0]]] : arr;
  return arr.reduce(
    (acc, item, i) =>
      acc.concat(
        permutations([...arr.slice(0, i), ...arr.slice(i + 1)]).map((val) => [
          item,
          ...val
        ])
      ),
    []
  );
};

Sie können den Code testen, indem Sie die permutations()-Funktion mit einem Array-Argument aufrufen:

permutations([1, 33, 5]);
// [ [1, 33, 5], [1, 5, 33], [33, 1, 5], [33, 5, 1], [5, 1, 33], [5, 33, 1] ]

Zusammenfassung

Herzlichen Glückwunsch! Sie haben das Array-Permutationen-Lab abgeschlossen. Sie können in LabEx weitere Labs absolvieren, um Ihre Fähigkeiten zu verbessern.