Encontrar todas las combinaciones de valores de matriz de JavaScript

Question

¿Cómo puedo producir todas las combinaciones de valores en N número de matrices de JavaScript de longitud variable?

Digamos que tengo N cantidad de matrices de JavaScript, p.

var first = ['a', 'b', 'c', 'd']; 
var second = ['e']; 
var third = ['f', 'g', 'h', 'i', 'j']; 

(tres matrices en este ejemplo, pero su número N de matrices para el problema.)

Y quiero salida de todas las combinaciones de sus valores, para producir

aef 
aeg 
aeh 
aei 
aej 
bef 
beg 
.... 
dej 

---

EDITAR: Esta es la versión que obtuve trabajando, usando la respuesta aceptada de ffriend como base.

var allArrays = [['a', 'b'], ['c', 'z'], ['d', 'e', 'f']]; 

function allPossibleCases(arr) { 
    if (arr.length === 0) { 
    return []; 
    } 
else if (arr.length ===1){ 
return arr[0]; 
} 
else { 
    var result = []; 
    var allCasesOfRest = allPossibleCases(arr.slice(1)); // recur with the rest of array 
    for (var c in allCasesOfRest) { 
     for (var i = 0; i < arr[0].length; i++) { 
     result.push(arr[0][i] + allCasesOfRest[c]); 
     } 
    } 
    return result; 
    } 

} 
var r=allPossibleCases(allArrays); 
//outputs ["acd", "bcd", "azd", "bzd", "ace", "bce", "aze", "bze", "acf", "bcf", "azf", "bzf"] 

Answer 1

Esto no es permutaciones, vea permutations definitions de Wikipedia.

Pero se puede lograr esto con recursividad:

var allArrays = [['a', 'b'], ['c'], ['d', 'e', 'f']] 

function allPossibleCases(arr) { 
    if (arr.length == 1) { 
    return arr[0]; 
    } else { 
    var result = []; 
    var allCasesOfRest = allPossibleCases(arr.slice(1)); // recur with the rest of array 
    for (var i = 0; i < allCasesOfRest.length; i++) { 
     for (var j = 0; j < arr[0].length; j++) { 
     result.push(arr[0][j] + allCasesOfRest[i]); 
     } 
    } 
    return result; 
    } 

} 

También puede hacerlo con bucles, pero va a ser un poco complicado y requerirá la implementación de su propia análogo de la pila.

Answer 2

No necesita recursividad, o bucles muy anidados, o incluso para generar/almacenar todo el conjunto de permutaciones en la memoria.

Dado que el número de permutaciones es el producto de las longitudes de cada una de las matrices (llamar a este numPerms), puede crear una función getPermutation(n) que devuelve una permutación única entre el índice de 0 y numPerms - 1 mediante el cálculo de los índices que necesita para recuperar sus personajes de, basado en n.

¿Cómo se hace esto? Si piensa en crear permutaciones en matrices que contengan cada una: [0, 1, 2, ... 9], es muy simple ... la 245ª permutación (n = 245) es "245", intuitivamente, o:

arrayHundreds[Math.floor(n/100) % 10] 
+ arrayTens[Math.floor(n/10) % 10] 
+ arrayOnes[Math.floor(n/1) % 10] 

La complicación en su problema es que los tamaños de matriz son diferentes. Podemos solucionar esto reemplazando el n/100, n/10, etc ... con otros divisores. Podemos precalcular fácilmente una matriz de divisores para este propósito. En el ejemplo anterior, el divisor de 100 era igual a arrayTens.length * arrayOnes.length. Por lo tanto, podemos calcular que el divisor de una matriz dada es el producto de las longitudes de las matrices restantes. La última matriz siempre tiene un divisor de 1. Además, en lugar de modificar por 10, modificamos por la longitud de la matriz actual.

Ejemplo de código es el siguiente:

var allArrays = [first, second, third, ...]; 

// Pre-calculate divisors 
var divisors = []; 
for (var i = allArrays.length - 1; i >= 0; i--) { 
    divisors[i] = divisors[i + 1] ? divisors[i + 1] * allArrays[i + 1].length : 1; 
} 

function getPermutation(n) { 
    var result = "", curArray; 

    for (var i = 0; i < allArrays.length; i++) { 
     curArray = allArrays[i]; 
     result += curArray[Math.floor(n/divisors[i]) % curArray.length]; 
    } 

    return result; 
} 

Answer 3

respuestas Apariencia demasiado difícil para mí.Así que mi solución es:

var allArrays = new Array(['a', 'b'], ['c', 'z'], ['d', 'e', 'f']); 

function getPermutation(array, prefix) { 
    prefix = prefix || ''; 
    if (!array.length) { 
     return prefix; 
    } 

    var result = array[0].reduce(function (result, value) { 
     return result.concat(getPermutation(array.slice(1), prefix + value)); 
    }, []); 
    return result; 
} 

console.log(getPermutation(allArrays)); 

Answer 4

Puede utilizar un retroceso típica:

function cartesianProductConcatenate(arr) { 
    var data = new Array(arr.length); 
    return (function* recursive(pos) { 
    if(pos === arr.length) yield data.join(''); 
    else for(var i=0; i<arr[pos].length; ++i) { 
     data[pos] = arr[pos][i]; 
     yield* recursive(pos+1); 
    } 
    })(0); 
} 

Solía ​​funciones del generador para evitar la asignación de todos los resultados al mismo tiempo, pero si se desea se puede

[...cartesianProductConcatenate([['a', 'b'], ['c', 'z'], ['d', 'e', 'f']])]; 
// ["acd","ace","acf","azd","aze","azf","bcd","bce","bcf","bzd","bze","bzf"] 

Answer 5

Sugiero un simple recursivo generator function de la siguiente manera:

// Generate all combinations of array elements: 
 
function* combinations(head, ...tail) { 
 
    let remainder = tail.length ? combinations(...tail) : [[]]; 
 
    for (let r of remainder) for (let h of head) yield [h, ...r]; 
 
} 
 

 
// Example: 
 
let first = ['a', 'b', 'c', 'd']; 
 
let second = ['e']; 
 
let third = ['f', 'g', 'h', 'i', 'j']; 
 

 
for (let c of combinations(first, second, third)) { 
 
    console.log(...c); 
 
}

Answer 6

copia de la respuesta le_m para tomar matriz de matrices directamente:

function *combinations(arrOfArr) { 
    let [head, ...tail] = arrOfArr 
    let remainder = tail.length ? combinations(tail) : [[]]; 
    for (let r of remainder) for (let h of head) yield [h, ...r]; 
} 

espero que ahorra tiempo de alguien.

Answer 7

Aquí hay una versión adaptada de la pareja anterior de respuestas, que produce los resultados en el orden especificado en la OP, y devuelve cadenas en lugar de matrices:

function *cartesianProduct(...arrays) { 
    if (!arrays.length) yield []; 
    else { 
    const [tail, ...head] = arrays.reverse(); 
    const beginning = cartesianProduct(...head.reverse()); 
    for (let b of beginning) for (let t of tail) yield b + t; 
    } 
} 

const first = ['a', 'b', 'c', 'd']; 
const second = ['e']; 
const third = ['f', 'g', 'h', 'i', 'j']; 
console.log([...cartesianProduct(first, second, third)]) 

Answer 8

Si usted está buscando un Flow función compatible que puede manejar matrices bidimensionales con cualquier tipo de elemento, puede utilizar la función a continuación.

const getUniqueCombinations = <T>(items : Array<Array<T>>, prepend : Array<T> = []) : Array<Array<T>> => { 
    if(!items || items.length === 0) return [prepend]; 

    let out = []; 

    for(let i = 0; i < items[0].length; i++){ 
     out = [...out, ...getUniqueCombinations(items.slice(1), [...prepend, items[0][i]])]; 
    } 

    return out; 
} 

Una visualización de la operación:

en:

[ 
    [Obj1, Obj2, Obj3], 
    [Obj4, Obj5], 
    [Obj6, Obj7] 
] 

a cabo:

[ 
    [Obj1, Obj4, Obj6 ], 
    [Obj1, Obj4, Obj7 ], 
    [Obj1, Obj5, Obj6 ], 
    [Obj1, Obj5, Obj7 ], 
    [Obj2, Obj4, Obj6 ], 
    [Obj2, Obj4, Obj7 ], 
    [Obj2, Obj5, Obj6 ], 
    [Obj2, Obj5, Obj7 ], 
    [Obj3, Obj4, Obj6 ], 
    [Obj3, Obj4, Obj7 ], 
    [Obj3, Obj5, Obj6 ], 
    [Obj3, Obj5, Obj7 ] 
]