Recherche de toutes les combinaisons de valeurs de tableau JavaScript

Question

Comment puis-je produire toutes les combinaisons de valeurs dans N nombre de tableaux JavaScript de longueurs variables?

Disons que j'ai N nombre de tableaux JavaScript, par ex.

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

(Trois tableaux dans cet exemple, mais son nombre N de tableaux pour le problème.)

Et je veux sortie toutes les combinaisons de leurs valeurs, pour produire

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

---

EDIT: Voici la version que j'ai commencé à travailler, en utilisant la réponse acceptée de Ffriend comme 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

Ceci n'est pas permutations, voir permutations definitions de Wikipedia.

Mais vous pouvez y parvenir avec récursion:

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; 
    } 

} 

Vous pouvez aussi le faire avec des boucles, mais il sera un peu difficile et aurez besoin d'implémenter votre propre analogique de la pile.

Answer 2

Vous n'avez pas besoin de récursion ou de boucles fortement imbriquées, ni même de générer/stocker l'ensemble des permutations en mémoire.

Comme le nombre de permutations est le produit des longueurs de chacun des réseaux (appeler ce numPerms), vous pouvez créer une fonction getPermutation(n) qui retourne une permutation unique entre index 0 et numPerms - 1 en calculant les indices dont il a besoin pour récupérer ses caractères à partir de, basé sur n.

Comment cela est-il fait? Si vous pensez créer des permutations sur des tableaux contenant chacun: [0, 1, 2, ... 9] c'est très simple ... la 245ème permutation (n = 245) est "245", plutôt intuitivement, ou:

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

La complication dans votre problème est que les tailles de tableau diffèrent. Nous pouvons contourner ce problème en remplaçant les n/100, n/10, etc ... par d'autres diviseurs. Nous pouvons facilement pré-calculer un tableau de diviseurs à cette fin. Dans l'exemple ci-dessus, le diviseur de 100 était égal à arrayTens.length * arrayOnes.length. Par conséquent, nous pouvons calculer le diviseur d'un tableau donné comme étant le produit des longueurs des tableaux restants. Le tout dernier tableau a toujours un diviseur de 1. De plus, au lieu de modder par 10, nous modifions la longueur du tableau courant.

Exemple de code est ci-dessous:

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

réponses fournies semble trop difficile pour moi.Donc, ma solution est:

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

Vous pouvez utiliser un retour en arrière typique:

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); 
} 

je les fonctions de générateur pour éviter l'attribution de tous les résultats en même temps, mais si vous voulez vous pouvez

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

Answer 5

Je suggère une simple récursive generator function comme suit:

// 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

Copie de la réponse de le_m à prendre Tableau de tableaux directement:

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]; 
} 

espère que cela fait gagner du temps de quelqu'un.

Answer 7

Voici une version adaptée du couple au-dessus des réponses, qui produit les résultats dans l'ordre spécifié dans l'OP, et renvoie des chaînes au lieu de tableaux:

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 vous êtes à la recherche d'un accréditif fonction compatible qui peut gérer des tableaux bidimensionnels avec n'importe quel type d'élément, vous pouvez utiliser la fonction ci-dessous.

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; 
} 

Une visualisation de l'opération:

dans:

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

sur:

[ 
    [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 ] 
]