Trouver toutes les combinaisons de valeurs du tableau JavaScript

vous n'avez pas besoin de récursion, ou de boucles fortement imbriquées, ou même pour générer/stocker tout le tableau de permutations en mémoire.

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

Comment faire? Si vous pensez à créer des permutations sur des tableaux contenant chacun: [0, 1, 2, ... 9] c'est très simple... la permutation de la 245E (n=245) est "245", plutôt intuitive, 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 cela en remplaçant le n/100 , n/10 , etc... avec d'autres diviseurs. On peut aisément calculer un tableau de diviseurs à cette fin. Ci-dessus exemple, le diviseur de 100 était égal à arrayTens.length * arrayOnes.length . Par conséquent, nous pouvons calculer le diviseur pour un tableau donné pour être le produit des longueurs des autres tableaux. Le dernier tableau a toujours un diviseur de 1. En outre, au lieu de modder par 10, nous moddons par la longueur du tableau courant.

exemple de code 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;
}

fourni des réponses 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));

je suggère un simple récursif fonction génératrice comme suit:

// Generate cartesian product of given iterables:
function* cartesian(head, ...tail) {
  let remainder = tail.length ? cartesian(...tail) : [[]];
  for (let r of remainder) for (let h of head) yield [h, ...r];
}

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

console.log(...cartesian(first, second, third));

vous pouvez utiliser un backtracking 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);
}

j'ai utilisé des fonctions de générateur pour éviter d'allouer tous les résultats simultanément, 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"]

copie de la réponse de le_m pour prendre le tableau des 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];
}

J'espère que ça fera gagner du temps à quelqu'un.

si vous êtes à la recherche d'une fonction compatible flow qui peut gérer des tableaux bidimensionnels avec n'importe quel type d'article, 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]
]

:

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

la façon la plus facile de trouver les combinaisons

const arr1= [ 'a', 'b', 'c', 'd' ];
const arr2= [ '1', '2', '3' ];
const arr3= [ 'x', 'y', ];

const all = [arr1, arr2, arr3];

const output = all.reduce((acc, cu) => { 
    let ret = [];
      acc.map(obj => {
        cu.map(obj_1 => {
          ret.push(obj + '-' + obj_1) 
        });
      });
      return ret;
   })

console.log(output);

Voici une version adaptée du couple de réponses ci-dessus, 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)])

vous pouvez utiliser cette fonction aussi:

const result = (arrayOfArrays) => arrayOfArrays.reduce((t, i) => { let ac = []; for (const ti of t) { for (const ii of i) { ac.push(ti + '/' + ii) } } return ac })

result([['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j']])
// which will output [ 'a/e/f', 'a/e/g', 'a/e/h','a/e/i','a/e/j','b/e/f','b/e/g','b/e/h','b/e/i','b/e/j','c/e/f','c/e/g','c/e/h','c/e/i','c/e/j','d/e/f','d/e/g','d/e/h','d/e/i','d/e/j']

bien sûr, vous pouvez supprimer le + '/' dans ac.push(ti + '/' + ii) pour éliminer la culture du résultat final. Et vous pouvez remplacer ces for (... of ...) par des fonctions forEach (plus le point-virgule respectif avant return ac ), quel que soit ceux avec lesquels vous êtes plus à l'aise.

vous pourriez prendre une approche en ligne simple en générant un produit cartésien.

result = items.reduce(
    (a, b) => a.reduce(
        (r, v) => r.concat(b.map(w => [].concat(v, w))),
        []
    )
);

var items = [['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j']],
    result = items.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));
	
console.log(result.map(a => a.join(' ')));

.as-console-wrapper { max-height: 100% !important; top: 0; }