Estoy tratando de resolver un algoritmo simple usando JS:
Dados dos números n y k, tienes que encontrar todas las combinaciones posibles de k números de 1…n.
Input : n = 5 k = 3 Output : 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5Sin embargo, cuando probé este código usando JS, no obtengo el resultado esperado:
let ans = [], arr = []; function makeCombination(n, k, low = 1) { if (k == 0) { ans.push(arr); console.log(...arr); return; } for (let i = low; i <= n; i++) { arr.push(i); makeCombination(n, k - 1, i + 1); arr.pop(); } return ans; } var n = 5; var k = 3; makeCombination(n, k);Producción:
1 2 3 1 2 4 1 2 5¿Pueden ayudarme, por qué no obtengo el resultado esperado? Apreciaría cualquiera de su ayuda.
let ans = [], arr = []; function makeCombination(n, k, low = 1) { if (k == 0) { ans.push(arr.slice()); // console.log(...arr); commenting out the console log to demonstrate that the returned value is correct return; } for (let i = low; i <= n; i++) { arr.push(i); makeCombination(n, k - 1, i + 1); arr.pop(); } return ans; } var n = 5; var k = 3; makeCombination(n, k).map(a => console.log(...a)); .as-console-wrapper { max-height: 100% !important; top: 0; }Debe hacer una copia de la matriz de resultados parciales. De lo contrario, inserta una referencia a la misma matriz en la matriz de resultados y elimina los elementos durante su algoritmo de retroceso.
Una señal reveladora del problema fue que su función escribió los resultados correctos en la consola, pero la matriz de resultados devuelta se llenó con matrices vacías. Usando slice() haces una copia que evita este problema.
Editar: copió la técnica de formateo de la consola de Nina Scholz porque se ve mucho mejor.
Además de usar algunas otras variables fuera de la función, puede tomar una función que devuelva una sola matriz.
function makeCombination(n, k, i = 1) { const result = []; while (i <= n - k + 1) { if (k === 1) result.push([i]); else result.push(...makeCombination(n, k - 1, i + 1).map(a => [i, ...a])); i++; } return result; } makeCombination(5, 3).map(a => console.log(...a)); .as-console-wrapper { max-height: 100% !important; top: 0; }