Поиск всех комбинаций значений массива JavaScript

Question

Как мне получить все комбинации значений в N количестве массивов JavaScript переменной длины?

Допустим, у меня есть N ряд массивов JavaScript, например,

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

(Три массива в этом примере, но это N количество массивов для задачи.)

И я хочу вывести все комбинации их значений, чтобы получить

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

---

РЕДАКТИРОВАТЬ: Вот версия, которую я получил работать, используя принятый ответ друга в качестве основы.

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

Это не перестановки, см. определения перестановок из Википедии.

Но вы можете достичь этого с помощью рекурсии :

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

}

Вы также можете сделать это с помощью циклов, но это будет немного сложнее и потребует реализации собственного аналога стека.

Answer 2

Вам не нужны рекурсия, или сильно вложенные циклы, или даже генерация / сохранение всего массива перестановок в памяти.

Поскольку число перестановок является произведением длин каждой изВ массивах (назовите это numPerms), вы можете создать функцию getPermutation(n), которая возвращает уникальную перестановку между индексами 0 и numPerms - 1, вычисляя индексы, из которых нужно извлечь свои символы, на основе n.

Как это сделать?Если вы думаете о создании перестановок для массивов, каждый из которых содержит: [0, 1, 2, ... 9], это очень просто ... 245-я перестановка (n = 245) - это "245", довольно интуитивно, или:

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

Сложность вашей проблемы в том, что размеры массивов различаются.Мы можем обойти это, заменив n/100, n/10 и т. Д. Другими делителями.Для этой цели мы можем легко предварительно рассчитать массив делителей.В приведенном выше примере делитель 100 был равен arrayTens.length * arrayOnes.length.Поэтому мы можем вычислить делитель для данного массива, который будет произведением длин оставшихся массивов.Самый последний массив всегда имеет делитель 1. Кроме того, вместо модуляции на 10 мы модифицируем длину текущего массива.

Пример кода ниже:

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

Я предлагаю простую рекурсивную функцию генератора следующим образом:

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

Answer 4

Предоставленные ответы выглядят слишком сложными для меня.Итак, мое решение:

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 5

Копия ответа le_m для непосредственного получения массива массивов:

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

Надеюсь, это сэкономит кому-то время.

Answer 6

Вы можете использовать типичный возврат:

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

Я использовал функции генератора, чтобы избежать одновременного распределения всех результатов, но при желании вы можете

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

Answer 7

Вы можете использовать однолинейный подход, генерируя декартово произведение.

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

Answer 8

Самый простой способ найти комбинации

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

Answer 9

Если вы ищете совместимую с потоком функцию, которая может обрабатывать двумерные массивы с любым типом элемента, вы можете использовать функцию ниже.

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

Визуализация операции:

в

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

Answer 10

Массивный подход без рекурсии:

const combinations = [['1', '2', '3'], ['4', '5', '6'], ['7', '8']];
let outputCombinations = combinations[0]

combinations.slice(1).forEach(row => {
  outputCombinations = outputCombinations.reduce((acc, existing) =>
    acc.concat(row.map(item => existing + item))
  , []);
});

console.log(outputCombinations);