Comment générer toutes les permutations d'un tableau en JavaScript ?

Comment calculer des permutations en JavaScript ?

Les permutations font référence à la génération de toutes les séquences possibles à partir d'un tableau. En JavaScript, un tableau d'entiers peut être permuté à l'aide de plusieurs approches différentes.

Approche avec mémorisation

Une approche consiste à utiliser la récursivité et la mémorisation pour garder une trace des permutations précédemment calculées. Voici une implémentation :

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;
}

Approche avec un tableau non mutant

Une autre approche utilise une technique de découpage non mutant pour éviter d'altérer le tableau d'origine :

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;
}

Version ES6

Une implémentation ES6 du non-mutant approche :

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;
};

Exemple d'entrée et de sortie

Par exemple, avec le tableau d'entrée suivant :

[1, 2, 3]

Les fonctions de permutation produiront :

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

Ces permutations sont générées en explorant toutes les combinaisons possibles des éléments du tableau d'entrée, en garantissant que chaque élément est utilisé exactement une fois dans chaque permutation.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!