Permutaciones en JavaScript
En JavaScript, hay slice, reduce, filter, substring, y muchos más métodos para aliviar el problema básico de permutar todas las pruebas posibles de una cadena o matriz determinada.
Aquí, mostraremos cómo extraer la combinación de matrices y cadenas de una entrada dada. El enfoque principal es dividir cada literal del array o cadena e intercambiar otros literales uno por uno.
En las siguientes secciones, analizaremos el procedimiento en detalle con los ejemplos de código necesarios.
Permutación de un array dada
Inicializaremos una función permutar con otra función backtrack dentro de ella. Esta función backtrack se llamará recursivamente para ejecutar el conjunto adecuado de combinaciones.
Fragmento de código:
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]);
Producción:
La acción principal aquí define la parte de intercambio, donde intercambiamos cada literal entre sí de una prueba (por ejemplo, [1,2,3]) y sacamos las combinaciones probables.
De la prueba [1,2,3], obtendremos [1,2,3] y [1,3,2]. Esta parte se ejecutará hasta que cada literal obtenga una verificación.
Antes de cambiar a la siguiente prueba, volvimos a la prueba base (1,2,3) intercambiando nuevamente (ya que la última combinación fue [1,3,2]). Así es como se opera el backtracking.
Se forma un árbol para ver las posibles pruebas, y la longitud del árbol es igual a la longitud del array. Inicialmente, realizamos un DFS para resolver el caso, y el procedimiento de retroceso recursivo lo hace.
Permutación en una cadena dada
En el caso de una cadena, primero dividiremos la cadena, y luego usaremos el método reduce para concatenar los intentos probables uno por uno llamando recursivamente a la función permutationString.
Fragmento de código:
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'));
Producción:
De acuerdo con la función del acumulador, estamos conservando cada combinación.
Usamos el método slice para bloquear un cierto alfabeto y agregar el resto de los alfabetos según el caso base inicializado antes. Finalmente, la salida da como resultado la forma combinada de todos los patrones esperados.
Las fórmulas factoriales derivan la permutación del método y, por lo tanto, la solución a este problema a menudo se encuentra con runtime error para casos grandes. Pero la inferencia básica del problema con una visualización adecuada se puede dirigir de esta manera.
