Permutations en JavaScript

1. Permutation d’un tableau donné
2. Permutation sur une chaîne donnée

En JavaScript, il y a slice, reduce, filter, substring, et bien d’autres méthodes pour résoudre le problème de base de la permutation de tous les essais possibles d’une chaîne ou d’un tableau donné.

Ici, nous allons montrer comment extraire la combinaison de tableaux et de chaînes à partir d’une entrée donnée. L’objectif principal est de diviser chaque littéral du tableau ou de la chaîne et d’échanger les autres littéraux un par un.

Dans les sections suivantes, nous discuterons de la procédure en détail avec les exemples de code nécessaires.

Permutation d’un tableau donné

Nous allons initialiser une fonction permute avec une autre fonction backtrack en son sein. Cette fonction backtrack sera récursivement appelée pour exécuter le bon ensemble de combinaisons.

Extrait de code:

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]);

Production :

L’action majeure définit ici la partie d’échange, où nous échangeons chaque littéral l’un avec l’autre d’un essai (e.g. [1,2,3]) et faisons ressortir les combinaisons probables.

A partir de l’essai [1,2,3], on obtiendra [1,2,3] & [1,3,2]. Cette partie sera exécutée jusqu’à ce que chaque littéral reçoive une vérification.

Avant de passer à l’essai suivant, nous sommes revenus à l’essai de base (1,2,3) en permutant à nouveau (car la dernière combinaison était [1,3,2]). C’est ainsi que s’opère le retour en arrière.

Un arbre est formé pour voir les essais possibles, et la longueur de l’arbre est égale à la longueur du tableau. Dans un premier temps, nous effectuons un DFS pour résoudre le cas, et la procédure de retour arrière récursif le fait.

Permutation sur une chaîne donnée

Dans le cas d’une chaîne, nous allons d’abord splitter la chaîne, puis nous utiliserons la méthode reduce pour concaténer les essais probables un par un en appelant récursivement la fonction permutationString.

Extrait de code:

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'));

Production :

Selon la fonction d’accumulateur, nous préservons chaque combinaison.

Nous utilisons la méthode slice pour verrouiller un certain alphabet et ajouter le reste des alphabets selon le cas de base initialisé auparavant. Enfin, la sortie résulte sous la forme combinée de tous les modèles attendus.

Les formules factorielles dérivent la permutation de méthode, et donc la solution à ce problème rencontre souvent l'erreur d'exécution pour les grands cas. Mais l’inférence de base pour le problème avec une visualisation appropriée peut être dirigée de cette façon.