estas funciones recursivas funcionan bien para obtener combinaciones de valores de una matriz:
function combinations(set, k) { if (k > set.length || k <= 0) return [] if (k === set.length) return [set] if (k === 1) return set.map(x => [x]) return set.reduce((p, c, i) => { combinations(set.slice(i + 1), k - 1).forEach(tailArray => p.push([c].concat(tailArray)), ) return p }, []) }Traté de convertir eso a una versión generativa:
function* combinations(set, k) { if (k > set.length || k <= 0) yield [] if (k === set.length) yield set if (k === 1) yield* set.map(x => [x]) for (let i in set) { for (const next of combinations(set.slice(+i + 1), k - 1)) { yield [set[i]].concat(next) } } return }sin embargo, esto devuelve muchos más resultados de los que debería, y no tienen la longitud correcta
function timeFn(fn){ const pre = performance.now() const r = fn() const post = performance.now() console.log('time', (post - pre)/1000 , 's') return r } timeFn(()=> [...combinations([...Array(4)].map((_,i)=>i+1), 3)]) VM2045:5 time 0.00009999999403953553 s (20) [Array(3), Array(3), Array(3), Array(4), Array(3), Array(3), Array(3), Array(3), Array(3), Array(3), Array(2), Array(3), Array(3), Array(3), Array(3), Array(3), Array(2), Array(1), Array(2), Array(1)]lamentablemente, no es solo para... en:
function* combinations(set, k) { if (k > set.length || k <= 0) yield [] if (k === set.length) yield set if (k === 1) yield* set.map(x => [x]) for (let i=0,lim=set.length; i<lim; i++) { for (const next of combinations(set.slice(i + 1), k - 1)) { yield [set[i]].concat(next) } } return } undefined timeFn(()=> [...combinations([...Array(4)].map((_,i)=>i+1), 3)]) VM2045:5 time 0.00020000000298023223 s (20) [Array(3), Array(3), Array(3), Array(4), Array(3), Array(3), Array(3), Array(3), Array(3), Array(3), Array(2), Array(3), Array(3), Array(3), Array(3), Array(3), Array(2), Array(1), Array(2), Array(1)]No ha convertido correctamente los casos base a la versión del generador:
if (k > set.length || k <= 0) return [] if (k === set.length) return [set] if (k === 1) return set.map(x => [x]) Tenga en cuenta que estos return , mientras su función de generador continúa, emitiéndolos todos .
function* combinations(set, k) { if (k > set.length || k <= 0) { // notice this yields nothing return } if (k === set.length) { yield set return } if (k === 1) { yield* set.map(x => [x]) return } for (let i=0; i<set.length; i++) { for (const next of combinations(set.slice(i + 1), k - 1)) { yield [set[i]].concat(next) } } } Por cierto, k === set.length y k === 1 no son casos base sino optimizaciones (innecesarias), y sus funciones no funcionan correctamente para k === 0 , eso debería generar una matriz vacía. Mejor:
function* combinations(set, k) { if (k >= 0 && k <= set.length) { if (k == 0) { yield []; } else { for (const [i, v] of set.entries()) for (const next of combinations(set.slice(i + 1), k - 1)) { yield [v, ...next]; } } } } }