javascript - resueltos - Permutaciones sin llamada a función recursiva
recursividad ejemplos resueltos (8)
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
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''
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.
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 totalesfactorial(len)de un conjunto de diferentes elementoslen. -
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
0es el conjunto en el orden dado. -
El número de permutación
factorial(a.length)-1es el último: el conjuntoaen 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:
-
fse calcula primero comofactorial(len). -
Para cada paso,
fse divide porlen, dando exactamente el factorial anterior. -
ndividido por este nuevo valor defda el número de ranura entre las ranuraslenque 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. -
ndebe reducirse al número de permutación dentro de este espacio, que es el resto de la divisiónn / 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;
}
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 />");
}
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;
}
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
iyjdondei<jyperm[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 .
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.
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''])));
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])));