He intentado esta respuesta para encontrar todas las permutaciones de tamaño K = 6 de una matriz de cadenas, pero la matriz que estoy permutando es demasiado grande (~ 13,000 elementos, pero puedo garantizar que la mayoría serán duplicados), lo que significa Me estoy poniendo:
.... re-permuting with 6925/12972 node:internal/console/constructor:257 value: function(streamSymbol, string) { ^ RangeError: Maximum call stack size exceeded at console.value (node:internal/console/constructor:257:20) at console.log (node:internal/console/constructor:359:26) at permute (/home/path/to/code/permutation.js:22:17) at permute (/home/path/to/code/permutation.js:23:9) ..... re-permuting with 6924/12972 .... re-permuting with 6918/12972
Y luego muere. Supuse que esa es la recursividad que es el problema.
Sé que hay como máximo ~ 300 elementos únicos en mi entrada (que es como sé que muchos de los elementos de la matriz deben ser duplicados), pero no sé si son 10,000 instancias de un elemento, y luego el resto son individualmente elementos únicos o al menos K de cada elemento único. Debido a eso, no puedo simplemente introducirlos en un Conjunto, y tal vez haya menos de K de un elemento, por lo que no puedo simplemente crear una nueva entrada duplicando las nuevas K veces.
Aquí está mi versión ligeramente modificada (solo para facilitar la lectura y el registro) del código de la respuesta vinculada anterior (en una segunda mirada, este algoritmo está lejos de ser óptimo):
let permArr = []; let usedChars = []; let originalLength; /** * Subsets of permutations of an array * @param {any[]} input array of elements to permute * @param {number} subsetLength size of the subsets to return * @returns {Array[]} and array of arrays */ function permute(input, subsetLength = input.length) { let index let ch; originalLength ??= input.length; for (index = 0; index < input.length; index++) { ch = input.splice(index, 1)[0]; usedChars.push(ch); if (input.length == 0) { let toAdd = usedChars.slice(0, subsetLength); // resizing the returned array to size k if (!permArr.includes(toAdd)) permArr.push(toAdd); } console.log(`re-permuting with ${input.length}/${originalLength}`) permute(input, subsetLength); input.splice(index, 0, ch); usedChars.pop(); } return permArr };Y encontré esta respuesta pero no la sigo en absoluto, y esta otra respuesta es similar pero aún usa la recursividad.
¿Cómo puedo hacer esto sin recursividad/más rendimiento para que pueda manejar arreglos mucho más grandes? Estoy usando NodeJs y no soy reacio a usar diferentes tipos de datos.
No sé si son 10,000 instancias de un elemento, y luego el resto son elementos únicos individualmente o al menos K de cada elemento único. Debido a eso, no puedo simplemente introducirlos en un Conjunto, y tal vez haya menos de K de un elemento, por lo que no puedo simplemente crear una nueva entrada duplicando las nuevas K veces.
Así que solo agrúpalos y cuéntalos. Parece bastante simple:
function subsetPermutations(arr, size) { const counts = {}; for (const el of arr) { counts[el] = (counts[el] ?? 0) + 1; } const unique = Object.keys(counts); const result = Array.from({length: size}); function* recurse(depth) { if (depth == size) { yield result; } else { for (const el of unique) { if (counts[el]) { result[depth] = el; counts[el]--; yield* recurse(depth+1) counts[el]++; } } } } return recurse(0); } for (const perm of subsetPermutations(["a", "b", "b", "c", "c", "c"], 3)) { console.log(perm.join('-')); }Intenté esta respuesta para encontrar todas las permutaciones de tamaño K = 6, pero la matriz que estoy permutando es demasiado grande (~ 13,000 elementos), sin embargo, puedo garantizar que sé que hay como máximo ~ 300 elementos únicos
Eso sigue siendo aproximadamente 300 6 permutaciones, que es demasiado para ponerlas en una matriz. La función anterior está diseñada como un iterador para que pueda trabajar en el result actual en un bucle antes de que se mute en la siguiente iteración, para evitar cualquier sobrecarga de asignación, pero aún así llevará demasiado tiempo generarlos todos.
¿Cómo puedo hacer esto sin recursividad/más rendimiento para que pueda manejar arreglos mucho más grandes? Estoy usando NodeJs y no soy reacio a usar diferentes tipos de datos.
Puede usar un Map en lugar del objeto para counts , pero dudo que sea mucho más rápido para solo 300 elementos diferentes.
Evitar la recursión es innecesario ya que solo tiene 6 niveles de profundidad, no habrá un desbordamiento de pila a diferencia de su solución ineficiente. Pero para el rendimiento, aún puede probar este enfoque de generación dinámica de bucles anidados.