Imprima recursivamente todas las permutaciones de una cadena(Javascript)

string algorithm

Question

He visto versiones de esta pregunta para otros idiomas, pero no para JS.

¿Es posible hacer esto recursivamente en una función?

Entiendo que necesito tomar el primer elemento en la cadena y luego agregarlo a cada solución a la recursión en el resto de la cadena. Entonces, lógicamente, entiendo cómo debe ir la recursión. Simplemente no entiendo cómo agregar el primer carácter a cada una de las soluciones recursivas

var myString = "xyz";

function printPermut(inputString){
    var outputString;
    if(inputString.length === 0){
        return inputString;
    }
    if(inputString.length === 1){
        return inputString;
    }
    else{
       for(int i = 0; i<inputString.length(); i++){
           //something here like: 
           //outputString = outputString.concat(printPermut(inputString.slice(1))??
           //maybe store each unique permutation to an array or something?
       } 
    }
}

Answer 1

El problema de las permutaciones ha sido estudiado hasta la muerte. El algoritmo de Heap es una solución bien conocida. Aquí hay una versión en JS, que usa un generador:

function *permute(a, n = a.length) {
  if (n <= 1) yield a.slice();
  else for (let i = 0; i < n; i++) {
    yield *permute(a, n - 1);
    const j = n % 2 ? 0 : i;
    [a[n-1], a[j]] = [a[j], a[n-1]];
  }
}

console.log(Array.from(permute("xyz".split(''''))).map(perm => perm.join('''')));

permute está diseñado para tomar y generar matrices, no cadenas, por lo que dividimos la cadena en caracteres antes de llamarla y pegamos los caracteres nuevamente en cadenas antes de imprimir los resultados.

Answer 2

Escribamos una función que devuelva todas las permutaciones de una cadena como una matriz. Como no desea ninguna variable global, devolver las permutaciones es crucial.

function permut(string) {
    if (string.length < 2) return string; // This is our break condition

    var permutations = []; // This array will hold our permutations

    for (var i=0; i<string.length; i++) {
        var char = string[i];

        // Cause we don''t want any duplicates:
        if (string.indexOf(char) != i) // if char was used already
            continue;           // skip it this time

        var remainingString = string.slice(0,i) + string.slice(i+1,string.length); //Note: you can concat Strings via ''+'' in JS

        for (var subPermutation of permut(remainingString))
            permutations.push(char + subPermutation)

    }
    return permutations;
}

Para imprimirlos, solo itera sobre la matriz después:

var myString = "xyz";
permutations = permut(myString);
for (permutation of permutations)
    print(permutation) //Use the output method of your choice

Espero poder ayudarte con tu pregunta.

Answer 3

Use la función recursiva para iterar a través de la cadena

    

    function getPermutations(string) {
      var results = [];

      if (string.length === 1) 
      {
        results.push(string);
        return results;
      }

      for (var i = 0; i < string.length; i++) 
      {
        var firstChar = string[i];
        var otherChar = string.substring(0, i) + string.substring(i + 1);
        var otherPermutations = getPermutations(otherChar);
        
        for (var j = 0; j < otherPermutations.length; j++) {
          results.push(firstChar + otherPermutations[j]);
        }
      }
      return results;
    }
    
    var permutation = getPermutations(''YES'');
    console.log("Total permutation: "+permutation.length);
    console.log(permutation);