javascript - resueltos - Permutaciones sin llamada a función recursiva

recursividad ejemplos resueltos

Question

Requisito: Algoritmo para generar todas las combinaciones posibles de un conjunto, sin duplicados, o llamando a la función recursivamente para devolver resultados.

¿La mayoría, si no todas las respuestas proporcionadas en Permutaciones en JavaScript? llama recursivamente a una función desde un bucle u otra función para devolver resultados.

Ejemplo de llamada de función recursiva dentro del bucle

function p(a, b, res) {
  var b = b || [], res = res || [], len = a.length;
  if (!len) 
    res.push(b)
  else 
    for (var i = 0; i < len 
         // recursive call to `p` here
       ; p(a.slice(0, i).concat(a.slice(i + 1, len)), b.concat(a[i]), res)
       , i++
    );
  return res
}

p(["a", "b", "c"]);

La pregunta actual intenta crear la permutación dada en un proceso lineal, basándose en la permutación previa.

Por ejemplo, dada una matriz

var arr = ["a", "b", "c"];

para determinar el número total de permutaciones posibles

for (var len = 1, i = k = arr.length; len < i ; k *= len++);

k debe devolver 6 , o el número total de posibles permutaciones de arr ["a", "b", "c"]

Con el número total de permutaciones individuales determinado para un conjunto, la matriz resultante que contendría las seis permutaciones podría crearse y rellenarse utilizando Array.prototype.slice() , Array.prototype.concat() y Array.prototype.reverse()

var res = new Array(new Array(k));

res[0] = arr;

res[1] = res[0].slice(0,1).concat(res[0].slice(-2).reverse());

res[2] = res[1].slice(-1).concat(res[1].slice(0,2));

res[3] = res[2].slice(0,1).concat(res[2].slice(-2).reverse());

res[4] = res[3].slice(-2).concat(res[3].slice(0,1));

res[5] = res[4].slice(0,1).concat(res[4].slice(-2).reverse());

Intenté reproducir resultados basados ​​en el patrón que se muestra en el gráfico para un Algoritmo de permutación lexicográfica ordenado basado en uno publicado en Algoritmos prácticos en C ++ en Cálculo de permutaciones y preguntas de la entrevista de trabajo .

Parece haber un patrón que podría extenderse si el conjunto de entrada fuera, por ejemplo

["a", "b", "c", "d", "e"]

donde se esperarían 120 permutaciones.

Un ejemplo de un intento de llenar una matriz que se basa solo en permutación previa

// returns duplicate entries at `j`
var arr = ["a", "b", "c", "d", "e"], j = [];
var i = k = arr.length;
arr.forEach(function(a, b, array) {
 if (b > 1) {
  k *= b;
  if (b === i -1) {
    for (var q = 0;j.length < k;q++) {
      if (q === 0) {
       j[q] = array;
      } else {
       j[q] = !(q % i) 
              ? array.slice(q % i).reverse().concat(array.slice(0, q % i)) 
              : array.slice(q % i).concat(array.slice(0, q % i));
      }
    }
  }
 }
})

sin embargo, aún no se han podido realizar los ajustes necesarios en los parámetros para .slice() , .concat() , .reverse() en js anterior para pasar de una permutación a la siguiente; mientras solo usa la entrada de matriz anterior dentro de res para determinar la permutación actual, sin usar recursiva.

Se notó un balance de llamadas par e impar y se intentó usar el módulo % operador y la matriz de entrada .length para llamar a .reverse() o no en ["a", "b", "c", "d", "e"] matriz, aunque no produjo resultados sin entradas duplicadas.

El resultado esperado es que el patrón anterior podría reducirse a dos líneas llamadas sucesivamente durante la duración del proceso hasta que todas las permutaciones se completen y se completen; uno para llamar a .reverse() , llamar sin .reverse() ; por ejemplo, después de res[0] lleno

// odd , how to adjust `.slice()` , `.concat()` parameters 
// for array of unknown `n` `.length` ?
res[i] = res[i - 1].slice(0,1).concat(res[i - 1].slice(-2).reverse());
// even    
res[i] = res[1 - 1].slice(-1).concat(res[i - 1].slice(0,2));

Pregunta: ¿Qué ajustes al patrón anterior son necesarios, en particular parámetros, o índice, pasado .slice() , .concat() para producir todas las permutaciones posibles de un conjunto dado sin utilizar una llamada recursiva a la función de procesamiento actual?

var arr = ["a", "b", "c"];

for (var len = 1, i = k = arr.length; len < i; k *= len++);

var res = new Array(new Array(k));

res[0] = arr;

res[1] = res[0].slice(0, 1).concat(res[0].slice(-2).reverse());

res[2] = res[1].slice(-1).concat(res[1].slice(0, 2));

res[3] = res[2].slice(0, 1).concat(res[2].slice(-2).reverse());

res[4] = res[3].slice(-2).concat(res[3].slice(0, 1));

res[5] = res[4].slice(0, 1).concat(res[4].slice(-2).reverse());

console.log(res);

Editar, actualizar

He encontrado un proceso para utilizar el patrón descrito anteriormente para devolver permutaciones en orden lexicográfico para una entrada de hasta 4 .length , usando un solo bucle for . Los resultados esperados no se devuelven para la matriz con una .length de 5 .

El patrón se basa en el segundo cuadro en "Cálculo de permutaciones y preguntas de la entrevista de trabajo" ^{[ 0 ]} .

Preferiría no usar .splice() o .sort() para devolver resultados, aunque se usa aquí al intentar cumplir con el último requisito de "rotación" en cada columna. La variable r debe hacer referencia al index del primer elemento de la próxima permutación, lo que hace.

El uso de .splice() , .sort() podría incluirse si su uso seguía el patrón en el gráfico; aunque en js continuación, en realidad no lo hacen.

No estoy del todo seguro de que el problema con js continuación sea solo la siguiente declaración if (i % (total / len) === reset) , aunque esa parte requirió la mayor inversión de tiempo; sin embargo, aún no devuelve los resultados esperados.

Específicamente, ahora refiriéndose a la tabla, en rotación, por ejemplo 2 al índice 0 , 1 al índice 2 . Intenté lograr esto usando r , que es un índice negativo, para atravesar de derecha a izquierda para recuperar el siguiente elemento que debe colocarse en el index 0 de la "columna" adyacente.

En la siguiente columna, 2 se colocaría en el index 2 , 3 se colocaría en el index 0 . Esta es una parte, en la medida en que ha sido capaz de captar o depurar, hasta ahora, es el área donde se produce el error.

Nuevamente, devuelve los resultados esperados para [1,2,3,4] , aunque no para [1,2,3,4,5]

var arr = [1, 2, 3, 4];
for (var l = 1, j = total = arr.length; l < j ; total *= l++);
for (var i = 1
     , reset = 0
     , idx = 0
     , r = 0
     , len = arr.length
     , res = [arr]
     ; i < total; i++) {
  // previous permutation
  var prev = res[i - 1];
  // if we are at permutation `6` here, or, completion of all 
  // permutations beginning with `1`;
  // setting next "column", place `2` at `index` 0;
  // following all permutations beginning with `2`, place `3` at
  // `index` `0`; with same process for `3` to `4`
  if (i % (total / len) === reset) {
    r = --r % -(len);
    var next = prev.slice(r);
    if (r === -1) {
      // first implementation used for setting item at index `-1`
      // to `index` 0
      // would prefer to use single process for all "rotations",
      // instead of splitting into `if` , `else`, though not there, yet
      res[i] = [next[0]].concat(prev.slice(0, 1), prev.slice(1, len - 1)
               .reverse());
    } else {
      // workaround for "rotation" at from `index` `r` to `index` `0`
      // the chart does not actually use the previous permutation here,
      // but rather, the first permutation of that particular "column";
      // here, using `r` `,i`, `len`, would be 
      // `res[i - (i - 1) % (total / len)]`
      var curr = prev.slice();
      // this may be useful, to retrieve `r`, 
      // `prev` without item at `r` `index`
      curr.splice(prev.indexOf(next[0]), 1);
      // this is not optiomal
      curr.sort(function(a, b) {
        return arr.indexOf(a) > arr.indexOf(b)
      });
      // place `next[0]` at `index` `0`
      // place remainder of sorted array at `index` `1` - n
      curr.splice(0, 0, next[0])
      res[i] = curr
    }
    idx = reset;
  } else {
    if (i % 2) {
      // odd
      res[i] = prev.slice(0, len - 2).concat(prev.slice(-2)
              .reverse())
    } else {
      //  even
      --idx
      res[i] = prev.slice(0, len - (len - 1))
               .concat(prev.slice(idx), prev.slice(1, len + (idx)))
    }
  }
}
// try with `arr` : `[1,2,3,4,5]` to return `res` that is not correct;
// how can above `js` be adjusted to return correct results for `[1,2,3,4,5]` ?
console.log(res, res.length)

Recursos:

Generando permutación con Javascript

(Cuenta atrás) Lexicografía de la cabeza QuickPerm: (Formalmente Ejemplo_03 ~ Palíndromos)

Generando todas las permutaciones [no recursivas] (Intento de portar desde C++ a javascript jsfiddle http://jsfiddle.net/tvvvjf3p/ )

Cálculo de permutación sin recursión - Parte 2

permutaciones de una cadena usando iteración

iterative-permutation

Permutaciones por intercambio

Evaluación de algoritmos de permutación

Algoritmo de permutación sin recursión? Java

Algoritmo no recursivo para la permutación completa con elementos repetitivos?

Permutaciones de cadena en Java (no recursivo)

Generando permutaciones perezosamente

Cómo generar todas las permutaciones de una lista en Python

¿Se pueden generar todas las permutaciones de un conjunto o cadena en tiempo O (n log n)?

Encontrar la enésima permutación lexicográfica de ''0123456789''

Combinaciones y permutaciones

Answer 1

Aquí hay un fragmento de un enfoque que se me ocurrió por mi cuenta, pero naturalmente también pude encontrarlo descrito en otra parte :

generatePermutations = function(arr) {
  if (arr.length < 2) {
    return arr.slice();
  }
  var factorial = [1];
  for (var i = 1; i <= arr.length; i++) {
    factorial.push(factorial[factorial.length - 1] * i);
  }

  var allPerms = [];
  for (var permNumber = 0; permNumber < factorial[factorial.length - 1]; permNumber++) {
    var unused = arr.slice();
    var nextPerm = [];
    while (unused.length) {
      var nextIndex = Math.floor((permNumber % factorial[unused.length]) / factorial[unused.length - 1]);
      nextPerm.push(unused[nextIndex]);
      unused.splice(nextIndex, 1);
    }
    allPerms.push(nextPerm);
  }
  return allPerms;
};

Enter comma-separated string (e.g. a,b,c):
<br/>
<input id="arrInput" type="text" />
<br/>
<button onclick="perms.innerHTML = generatePermutations(arrInput.value.split('','')).join(''<br/>'')">
  Generate permutations
</button>
<br/>
<div id="perms"></div>

Explicación

Como hay permutaciones factorial(arr.length) para un arreglo dado arr , cada número entre 0 y factorial(arr.length)-1 codifica una permutación particular. Para descodificar un número de permutación, elimine repetidamente elementos de arr hasta que no queden elementos. El índice exacto de qué elemento eliminar está dado por la fórmula (permNumber % factorial(arr.length)) / factorial(arr.length-1) . Se podrían usar otras fórmulas para determinar el índice que se eliminará, siempre que conserve el mapeo uno a uno entre el número y la permutación.

Ejemplo

Lo siguiente es cómo se generarían todas las permutaciones para la matriz (a,b,c,d) :

#    Perm      1st El        2nd El      3rd El    4th El
0    abcd   (a,b,c,d)[0]   (b,c,d)[0]   (c,d)[0]   (d)[0]
1    abdc   (a,b,c,d)[0]   (b,c,d)[0]   (c,d)[1]   (c)[0]
2    acbd   (a,b,c,d)[0]   (b,c,d)[1]   (b,d)[0]   (d)[0]
3    acdb   (a,b,c,d)[0]   (b,c,d)[1]   (b,d)[1]   (b)[0]
4    adbc   (a,b,c,d)[0]   (b,c,d)[2]   (b,c)[0]   (c)[0]
5    adcb   (a,b,c,d)[0]   (b,c,d)[2]   (b,c)[1]   (b)[0]
6    bacd   (a,b,c,d)[1]   (a,c,d)[0]   (c,d)[0]   (d)[0]
7    badc   (a,b,c,d)[1]   (a,c,d)[0]   (c,d)[1]   (c)[0]
8    bcad   (a,b,c,d)[1]   (a,c,d)[1]   (a,d)[0]   (d)[0]
9    bcda   (a,b,c,d)[1]   (a,c,d)[1]   (a,d)[1]   (a)[0]
10   bdac   (a,b,c,d)[1]   (a,c,d)[2]   (a,c)[0]   (c)[0]
11   bdca   (a,b,c,d)[1]   (a,c,d)[2]   (a,c)[1]   (a)[0]
12   cabd   (a,b,c,d)[2]   (a,b,d)[0]   (b,d)[0]   (d)[0]
13   cadb   (a,b,c,d)[2]   (a,b,d)[0]   (b,d)[1]   (b)[0]
14   cbad   (a,b,c,d)[2]   (a,b,d)[1]   (a,d)[0]   (d)[0]
15   cbda   (a,b,c,d)[2]   (a,b,d)[1]   (a,d)[1]   (a)[0]
16   cdab   (a,b,c,d)[2]   (a,b,d)[2]   (a,b)[0]   (b)[0]
17   cdba   (a,b,c,d)[2]   (a,b,d)[2]   (a,b)[1]   (a)[0]
18   dabc   (a,b,c,d)[3]   (a,b,c)[0]   (b,c)[0]   (c)[0]
19   dacb   (a,b,c,d)[3]   (a,b,c)[0]   (b,c)[1]   (b)[0]
20   dbac   (a,b,c,d)[3]   (a,b,c)[1]   (a,c)[0]   (c)[0]
21   dbca   (a,b,c,d)[3]   (a,b,c)[1]   (a,c)[1]   (a)[0]
22   dcab   (a,b,c,d)[3]   (a,b,c)[2]   (a,b)[0]   (b)[0]
23   dcba   (a,b,c,d)[3]   (a,b,c)[2]   (a,b)[1]   (a)[0]

Tenga en cuenta que cada número de permutación tiene la forma:

(firstElIndex * 3!) + (secondElIndex * 2!) + (thirdElIndex * 1!) + (fourthElIndex * 0!)

que es básicamente el proceso inverso de la fórmula dada en la explicación.

Answer 2

Aquí hay una solución simple para calcular la enésima permutación de una cadena:

function string_nth_permutation(str, n) {
    var len = str.length, i, f, res;

    for (f = i = 1; i <= len; i++)
        f *= i;

    if (n >= 0 && n < f) {
        for (res = ""; len > 0; len--) {
            f /= len;
            i = Math.floor(n / f);
            n %= f;
            res += str.charAt(i);
            str = str.substring(0, i) + str.substring(i + 1);
        }
    }
    return res;
}

El algoritmo sigue estos simples pasos:

• primer cálculo f = len! , hay permutaciones totales factorial(len) de un conjunto de diferentes elementos len .
• como primer elemento, divida el número de permutación por (len-1)! y eligió el elemento en el desplazamiento resultante. Hay (len-1)! diferentes permutaciones que tienen cualquier elemento dado como primer elemento.
• elimine el elemento elegido del conjunto y use el resto de la división como número de permutación para continuar.
• Realice estos pasos con el resto del conjunto, cuya longitud se reduce en uno.

Este algoritmo es muy simple y tiene propiedades interesantes:

• Calcula la enésima permutación directamente.
• Si se ordena el conjunto, las permutaciones se generan en orden lexicográfico.
• Funciona incluso si los elementos establecidos no se pueden comparar entre sí, como objetos, matrices, funciones ...
• El número de permutación 0 es el conjunto en el orden dado.
• El número de permutación factorial(a.length)-1 es el último: el conjunto a en orden inverso.
• Las permutaciones fuera de este rango se devuelven como indefinidas.

Se puede convertir fácilmente para manejar un conjunto almacenado como una matriz:

function array_nth_permutation(a, n) {
    var b = a.slice();  // copy of the set
    var len = a.length; // length of the set
    var res;            // return value, undefined
    var i, f;

    // compute f = factorial(len)
    for (f = i = 1; i <= len; i++)
        f *= i;

    // if the permutation number is within range
    if (n >= 0 && n < f) {
        // start with the empty set, loop for len elements
        for (res = []; len > 0; len--) {
            // determine the next element:
            // there are f/len subsets for each possible element,
            f /= len;
            // a simple division gives the leading element index
            i = Math.floor(n / f);
            // alternately: i = (n - n % f) / f;
            res.push(b.splice(i, 1)[0]);
            // reduce n for the remaining subset:
            // compute the remainder of the above division
            n %= f;
            // extract the i-th element from b and push it at the end of res
        }
    }
    // return the permutated set or undefined if n is out of range
    return res;
}

aclaración:

• f se calcula primero como factorial(len) .
• Para cada paso, f se divide por len , dando exactamente el factorial anterior.
• n dividido por este nuevo valor de f da el número de ranura entre las ranuras len que tienen el mismo elemento inicial. Javascript no tiene división integral, podríamos usar (n / f) ... 0) para convertir el resultado de la división en su parte integral, pero introduce una limitación a conjuntos de 12 elementos. Math.floor(n / f) permite conjuntos de hasta 18 elementos. También podríamos usar (n - n % f) / f , probablemente también más eficiente.
• n debe reducirse al número de permutación dentro de este espacio, que es el resto de la división n / f .

Podríamos usar i diferente en el segundo ciclo, almacenando el resto de la división, evitando Math.floor() y el operador % adicional. Aquí hay una alternativa para este ciclo que puede ser aún menos legible:

        // start with the empty set, loop for len elements
        for (res = []; len > 0; len--) {
            i = n % (f /= len);
            res.push(b.splice((n - i) / f, 1)[0]);
            n = i;
        }

Answer 3

Aquí podría haber otra solución, inspirada en el algoritmo Steinhaus-Johnson-Trotter :

function p(input) {
  var i, j, k, temp, base, current, outputs = [[input[0]]];
  for (i = 1; i < input.length; i++) {
    current = [];
    for (j = 0; j < outputs.length; j++) {
      base = outputs[j];
      for (k = 0; k <= base.length; k++) {
        temp = base.slice();
        temp.splice(k, 0, input[i]);
        current.push(temp);
      }
    }
    outputs = current;
  }
  return outputs;
}

// call

var outputs = p(["a", "b", "c", "d"]);
for (var i = 0; i < outputs.length; i++) {
  document.write(JSON.stringify(outputs[i]) + "<br />");
}

Answer 4

Creo que esta post debería ayudarte. El algoritmo debe ser fácilmente traducible a JavaScript (creo que es más del 70% compatible con JavaScript).

slice y reverse son malas llamadas para usar si buscas eficiencia. El algoritmo descrito en la publicación sigue la implementación más eficiente de la función next_permutation, que incluso está integrada en algunos lenguajes de programación (como C ++, por ejemplo)

EDITAR

Al repetir el algoritmo una vez más, creo que puedes eliminar los tipos de variables y deberías usar JavaScript.

EDITAR

Versión de JavaScript:

function nextPermutation(array) {
    // Find non-increasing suffix
    var i = array.length - 1;
    while (i > 0 && array[i - 1] >= array[i])
        i--;
    if (i <= 0)
        return false;

    // Find successor to pivot
    var j = array.length - 1;
    while (array[j] <= array[i - 1])
        j--;
    var temp = array[i - 1];
    array[i - 1] = array[j];
    array[j] = temp;

    // Reverse suffix
    j = array.length - 1;
    while (i < j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i++;
        j--;
    }
    return true;
}

Answer 5

Me atrevo a agregar otra respuesta, con el objetivo de responder su pregunta sobre slice , concat , reverse .

La respuesta es que es posible (casi), pero no sería del todo efectivo. Lo que está haciendo en su algoritmo es lo siguiente:

• Encuentre la primera inversión en la matriz de permutación, de derecha a izquierda (inversión en este caso definida como i y j donde i < j y perm[i] > perm[j] , índices dados de izquierda a derecha)
• colocar el mayor número de inversión
• concatene los números procesados ​​en orden inverso, que será lo mismo que el orden ordenado, ya que no se observaron inversiones.
• concatenar el segundo número de la inversión (todavía ordenado de acuerdo con el número anterior, ya que no se observaron inversiones)

Esto es principalmente lo que hace mi primera respuesta, pero de una manera un poco más óptima.

Ejemplo

Considere la permutación 9,10, 11, 8, 7, 6, 5, 4, 3,2,1 La primera inversión de derecha a izquierda es 10, 11. Y realmente la siguiente permutación es: 9,11,1, 2,3,4,5,6,7,8,9,10 = 9concat (11) concat (rev (8,7,6,5,4,3,2,1)) concat (10)

Código fuente Aquí incluyo el código fuente como lo imagino:

var nextPermutation = function(arr) {
  for (var i = arr.length - 2; i >= 0; i--) {
     if (arr[i] < arr[i + 1]) {
        return arr.slice(0, i).concat([arr[i + 1]]).concat(arr.slice(i + 2).reverse()).concat([arr[i]]);
     }
  }
  // return again the first permutation if calling next permutation on last.
  return arr.reverse();
}

console.log(nextPermutation([9, 10, 11, 8, 7, 6, 5, 4, 3, 2, 1]));
console.log(nextPermutation([6, 5, 4, 3, 2, 1]));
console.log(nextPermutation([1, 2, 3, 4, 5, 6]));

El código está disponible para jsfiddle here .

Answer 6

Un código C ++ bastante simple sin recursividad.

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>

// Integer data
void print_all_permutations(std::vector<int> &data) {
    std::stable_sort(std::begin(data), std::end(data));
    do {
        std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " ")), std::cout << ''/n'';
    } while (std::next_permutation(std::begin(data), std::end(data)));
}

// Character data (string)
void print_all_permutations(std::string &data) {
    std::stable_sort(std::begin(data), std::end(data));
    do {
        std::copy(data.begin(), data.end(), std::ostream_iterator<char>(std::cout, " ")), std::cout << ''/n'';
    } while (std::next_permutation(std::begin(data), std::end(data)));
}

int main()
{
    std::vector<int> v({1,2,3,4});
    print_all_permutations(v);

    std::string s("abcd");
    print_all_permutations(s);

    return 0;
}

Podemos encontrar la próxima permutación de una secuencia en tiempo lineal.

Answer 7

Un método para crear permutaciones es agregar cada elemento en todos los espacios entre elementos en todos los resultados hasta el momento. Esto se puede hacer sin recurrencia utilizando bucles y una cola.

Código JavaScript:

function ps(a){
  var res = [[]];

  for (var i=0; i<a.length; i++){
    while(res[res.length-1].length == i){
      var l = res.pop();
      for (var j=0; j<=l.length; j++){
        var copy = l.slice();
        copy.splice(j,0,a[i]);
        res.unshift(copy);
      }
    }
  }
  return res;
}

console.log(JSON.stringify(ps([''a'',''b'',''c'',''d''])));

Answer 8

Aquí hay una respuesta de @le_m . Puede ser de ayuda.

El siguiente algoritmo muy eficiente utiliza el método de Heap para generar todas las permutaciones de N elementos con complejidad de tiempo de ejecución en O (N!):

function permute(permutation) {
  var length = permutation.length,
      result = [permutation.slice()],
      c = new Array(length).fill(0),
      i = 1, k, p;

  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i];
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
      ++c[i];
      i = 1;
      result.push(permutation.slice());
    } else {
      c[i] = 0;
      ++i;
    }
  }
  return result;
}

console.log(JSON.stringify(permute([1, 2, 3, 4])));