Permutationen in JavaScript

In JavaScript gibt es slice, reduce, filter, substring und viele weitere Methoden, um das grundlegende Problem der Permutation aller möglichen Versuche eines gegebenen Strings oder Arrays zu lösen.

Hier zeigen wir, wie man die Kombination von Arrays und Strings aus einer gegebenen Eingabe herauszieht. Das Hauptaugenmerk liegt darauf, jedes Literal aus dem Array oder String zu trennen und andere Literale einzeln auszutauschen.

In den folgenden Abschnitten gehen wir ausführlich auf die Vorgehensweise mit notwendigen Codebeispielen ein.

Permutation eines gegebenen Arrays

Wir werden eine Funktion permute mit einer anderen Funktion backtrack darin initialisieren. Diese Funktion backtrack wird rekursiv aufgerufen, um den richtigen Satz von Kombinationen auszuführen.

Code-Auszug:

var permute = function(nums) {
  var result = [];
  var backtrack = (i, nums) => {
    if (i === nums.length) {
      result.push(nums.slice());
      return;
    }
    for (let j = i; j < nums.length; j++) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      backtrack(i + 1, nums);
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  } backtrack(0, nums);
  console.log(result);
  return result;
};
permute([1, 2, 3]);

Ausgabe:

Die Hauptaktion definiert hier den Austauschteil, in dem wir jedes Literal eines Versuchs (z. B. [1,2,3]) gegeneinander austauschen und die wahrscheinlichen Kombinationen hervorbringen.

Aus dem Versuch [1,2,3] erhalten wir [1,2,3] & [1,3,2]. Dieser Teil wird ausgeführt, bis jedes Literal überprüft wird.

Bevor wir zum nächsten Versuch wechselten, kehrten wir zum Basisversuch (1,2,3) zurück, indem wir erneut tauschten (da die letzte Kombination [1,3,2] war). So wird das Backtracking betrieben.

Ein Baum wird gebildet, um die möglichen Versuche zu sehen, und die Baumlänge ist gleich der Feldlänge. Zunächst führen wir ein DFS zur Lösung des Falls durch, und das rekursive Backtracking-Verfahren erledigt dies.

Permutation auf einem gegebenen String

Im Falle einer Zeichenkette werden wir zuerst die Zeichenkette aufteilen und dann die Methode reduzieren verwenden, um die wahrscheinlichen Versuche einen nach dem anderen zu verketten, indem wir rekursiv die Funktion permutationString aufrufen.

Code-Auszug:

var permutationString = str => {
  if (str.length <= 2)
    return str.length === 2 ? [str[0] + str[1], str[1] + str[0]] : [str];
  return str.split('').reduce(
      (accumulator, letter, i) => accumulator.concat(
          permutationString(str.slice(0, i) + str.slice(i + 1))
              .map(val => letter + val)),
      []);
};
console.log(permutationString('abcd'));

Ausgabe:

Gemäß der Akkumulatorfunktion bewahren wir jede Kombination.

Wir verwenden die slice-Methode, um ein bestimmtes Alphabet zu sperren und die restlichen Alphabete gemäß dem zuvor initialisierten Basisfall hinzuzufügen. Schließlich ergibt sich die Ausgabe in der kombinierten Form aller erwarteten Muster.

Die faktoriellen Formeln leiten die Methodenpermutation ab, und daher trifft die Lösung dieses Problems für große Fälle häufig auf Laufzeitfehler. Aber die grundlegende Schlussfolgerung für das Problem mit einer richtigen Visualisierung kann in diese Richtung gelenkt werden.