Wie generiere ich alle Permutationen eines Arrays in JavaScript?

Wie berechnet man Permutationen in JavaScript?

Permutationen beziehen sich auf die Generierung aller möglichen Sequenzen aus einem Array. In JavaScript kann ein Array von ganzen Zahlen mit verschiedenen Ansätzen permutiert werden.

Ansatz mit Memoisierung

Ein Ansatz beinhaltet die Verwendung von Rekursion und Memoisierung, um zuvor berechnete Permutationen im Auge zu behalten. Hier ist eine Implementierung:

let permArr = [];
let usedChars = [];

function permute(input) {
  const chars = input.sort();  // Prevent duplicate permutations with identical values

  for (let i = 0; i < chars.length; i++) {
    const ch = chars.splice(i, 1);
    usedChars.push(ch);
    if (chars.length === 0) {
      permArr[permArr.length] = usedChars.join("");
    }
    permute(chars.join(""));
    chars.splice(i, 0, ch);
    usedChars.pop();
  }

  return permArr;
}

Ansatz mit nicht mutierendem Array

Ein anderer Ansatz verwendet eine nicht mutierende Slicing-Technik, um eine Änderung des ursprünglichen Arrays zu vermeiden:

function permutator(inputArr) {
  let result = [];

  function permute(arr, memo = []) {
    if (arr.length === 0) {
      result.push(memo);
    } else {
      for (let i = 0; i < arr.length; i++) {
        permute(arr.slice(0, i).concat(arr.slice(i + 1)), memo.concat(arr[i]));
      }
    }
  }

  permute(inputArr);

  return result;
}

ES6-Version

Eine ES6-Implementierung des Nicht-Mutierenden Ansatz:

const permutator = (inputArr) => {
  let result = [];

  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      result.push(m);
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next));
      }
    }
  };

  permute(inputArr);

  return result;
};

Beispieleingabe und -ausgabe

Zum Beispiel mit dem folgenden Eingabearray:

[1, 2, 3]

Die Permutationsfunktionen geben Folgendes aus:

[
  [ 1, 2, 3 ],
  [ 1, 3, 2 ],
  [ 2, 1, 3 ],
  [ 2, 3, 1 ],
  [ 3, 1, 2 ],
  [ 3, 2, 1 ]
]

Diese Permutationen werden generiert, indem alle möglichen Kombinationen der Eingabearray-Elemente untersucht werden, um sicherzustellen, dass jedes Element in jedem genau einmal verwendet wird Permutation.

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