Dados 3 caracteres ( abc ), quiero generar todas las cadenas de 5 letras posibles con ellos ( aaaab aaaaa ... ccccb , ccccc )
const s = 'byg'; const p = []; for (let i = 0; i < 3; i++) { for (let j = 0; j < 3; j++) { for (let k = 0; k < 3; k++) { for (let l = 0; l < 3; l++) { for (let m = 0; m < 3; m++) { p.push(s[i] + s[j] + s[k] + s[l] + s[m]); } } } } } console.log(p, p.length === 3 ** 5)Esto se siente como una forma ineficiente de hacer esto, entonces, ¿hay una forma más elegante/eficiente de hacerlo?
Escribes un algoritmo de combinación, pero si tienes un campo que es bueno, solo puedes hacer la probabilidad de longitud 3, porque necesitas hacerlo de nuevo.
function permutationAndCombination(source = [], selectedLimit, isPermutation = true) { if (!Array.isArray(source)) return source source = [...new Set(source)] selectedLimit = selectedLimit || source.length const result = [] const sourceLen = source.length selectedLimit = selectedLimit > sourceLen ? sourceLen : selectedLimit const innerLoop = (prefix = [], done = [], index = 0) => { const prefixLen = prefix.length for (let i = isPermutation ? 0 : index; i < sourceLen; i++) { if (prefixLen > selectedLimit - 1) break // Optimization: Continue to next cycle if current item has be already used for 'prefix'. if (done.includes(i)) continue const item = source[i] const newItem = [...prefix, item] if (prefixLen === selectedLimit - 1) { result.push(newItem) } if (prefixLen < selectedLimit - 1) { innerLoop(newItem, [...done, i], index++) } } } if (source.length) { // there is only one case if we want to select all items from source by combination. if (!isPermutation && selectedLimit === sourceLen) { return source } innerLoop() } return result } console.log(permutationAndCombination(['a','b','c'], 3));espero ayudarte
Tus bucles for anidados implican que el código se puede refactorizar usando recursividad o, como en mi ejemplo a continuación, creando un bucle de nivel superior.
Este enfoque nos permite generar cadenas de cualquier longitud deseada.
let characters = "abc"; let desiredLength = 5; let theSet = [""]; for ( let length = 0; length < desiredLength; length++){ let extendedSet = []; theSet.forEach( (item) => extendedSet.push( ...extendWith( item, characters) ) ) theSet = extendedSet; } console.log('result ', theSet); // given a strings and a set of characters // generate an array of string extended with each // of the characters. // "a" with "xy" generates // [ "ax", "ay" ] function extendWith( extendThis, characters){ let result = []; [...characters].forEach( (c) => result.push(extendThis+c) ); return result; }Podemos hacer que la función extendWith sea más sucinta como esta
function extendWith( extendThis, characters){ return [...characters].map( c => extendThis + c ); }y como ahora es solo una expresión de una línea, podemos prescindir de la función de utilidad y simplificar un poco más
for ( let length = 0; length < desiredLength; length++){ theSet = theSet.flatMap( (item) => [...characters].map( c => item + c ) ); }De hecho, es eficiente. Está tratando de producir una lista de 3^5 palabras, o más generalmente, n^k palabras, donde n es el número de letras y k es la longitud de cada palabra, por lo que O(n^k) es un límite inferior en la complejidad del tiempo, ya que solo escribir la salida en la memoria lleva al menos O (n ^ k) tiempo. k bucles anidados cada uno con n iteraciones te da este límite inferior. No puedes hacerlo mejor que eso.
El problema es que depender de bucles anidados codificados no es muy escalable. ¿Qué pasaría si quisiera palabras de 10 o 20 o incluso más? El enfoque recursivo podría ser mejor.
Editar:
Ahora que lo pienso, el límite inferior es en realidad O(k*n^k), ya que tiene n^k palabras cada una de longitud k. Pero aparte de eso, creo que mi análisis sigue siendo correcto. Esos bucles aún alcanzan el límite inferior.