Estoy usando javascript haciendo mi tarea. La pregunta es necesaria para encontrar todas las combinaciones de asignación de salas y reuniones con N salas y n reuniones.
Por ejemplo, si tengo 5 rooms y necesito asignarlas a 3 meetings , el resultado será algo como
[1,1,3],[1,2,2],[1,3,1],[2,1,2],[2,2,1] and [3,1,1] .
Necesito usar la recursividad para resolver esta pregunta. Pero mi recursividad solo me da un resultado en lugar de todos los resultados.
function partition(num, m) { if (m == 1) { return num } else { for (i = 1; i < num; i++) { return i + "," + partition(num - i, m - 1) } } } console.log(partition(5, 3))¿Cómo enumerar todas las combinaciones con recursividad? Estoy luchando por mucho tiempo. Muchísimas gracias.
Algunos asuntos:
Su código usa una variable global llamada i . Esto no es correcto, ya que la iteración del bucle en la recursividad cambiará la i que usan los bucles externos. Declare siempre sus variables en un ámbito local. Así for (let i.....)
Su función no debe generar una cadena a través de la concatenación ( + ) y devolver una cadena, ni debe devolver un número en el caso base, pero debe devolver una matriz de matrices, tal como lo ha representado en el resultado del ejemplo.
Entonces, el caso base debería devolver [[num]] . La matriz externa tiene solo un elemento, lo que representa que solo hay una partición posible, y la matriz interna especifica cuál es esa partición: solo tiene una habitación.
Dado que la llamada recursiva devuelve una matriz de matrices, debe iterar ese resultado recursivo y agregar la asignación de habitación actual para formar nuevas combinaciones.
La iteración puede detenerse un poco antes de lo previsto, ya que debe haber suficiente "valor" en num - i para llenar las habitaciones restantes con al menos 1.
Aquí hay una solución:
function partition(num, m) { if (m == 1) { return [[num]]; // return an array or arrays } else { let collect = []; // Prepare array for collecting the partitions // Quit loop when not enough value to distribute in remaining rooms for (let i = 1; i <= num - m + 1; i++) { // Iterate the arrays that come back from recursion... for (let arr of partition(num - i, m - 1)) { collect.push([i, ...arr]); // ... and extend them. } } return collect; } } console.log(partition(5, 3));Parece que ya sabes cómo generar las secuencias, así que simplemente describe las reglas que usaste en tu cabeza. Luego trabaje el programa hacia atrás desde allí. A continuación, describimos cómo generar combinaciones de tamaño fijo de tamaño k a partir de cualquier matriz, t -
k , es cero, da la combinación vacía, ()k es al menos uno. Si la matriz t está vacía, no queda nada para elegir. Detener iteraciónk es al menos uno y la matriz tiene al menos un elemento. Elija el primer elemento de t y agréguelo a cada combinación del subproblema, (t.slice(1), k - 1) . Y no elija este elemento y rinda del subproblema, (t.slice(1), k) . function* choosek(t, k) { if (k == 0) return (yield []) // 1 else if (t.length == 0) return // 2 else { // choose first element // 3 for (const c of choosek(t.slice(1), k - 1)) yield [t[0], ...c] // skip first element yield* choosek(t.slice(1), k) } } for (const c of choosek(["🔴","🟢","🔵","🟡","⚫️"], 3)) console.log(c.join("")) 🔴🟢🔵 🔴🟢🟡 🔴🟢⚫️ 🔴🔵🟡 🔴🔵⚫️ 🔴🟡⚫️ 🟢🔵🟡 🟢🔵⚫️ 🟢🟡⚫️ 🔵🟡⚫️ Una ventaja de usar una matriz como entrada en lugar de un número es que podemos generar combinaciones de tamaño fijo a partir de cualquier entrada, no solo numéricas. Y debido a que .slice también funciona en cadenas, ¡también podemos usar entradas basadas en cadenas!
for (const c of choosek("ABCDE", 3)) console.log(c.join("")) ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE