Декартово произведение нескольких массивов

Как можно реализовать декартово произведение нескольких массивов в JavaScript?
// например cartesian([1,2], [10,20], [100,200,300]) // будет равно // [[1, 10, 100], [1, 10, 200], [1, 10, 300], [1, 20, 100], [1, 20, 200], ...]

Ответ

Самый короткий способ на чистом JavaScript
const f = (a, b) => [].concat(...a.map(ai => b.map(bi => ai.concat([bi])))); const cartesian = (...arrays) => arrays.reduce((a, b) => f(a, b), [[]]);
Используются
методы для массивов .map, .reduce, .concat оператор расширения ... и синтаксис оставшихся аргументов
То же самое в виде одной функции с комментариями
const cartesian = (...arrays) => // итеративно получаем декартово произведение // нескольких первых массивов из arrays, // начиная с нуля массивов и пустого декартова произведения --- [[]] arrays.reduce((cartesianPart, array) => // сглаживание массива массивов [].concat(... // cartesianPart --- декартово произведение нескольких первых массивов из arrays cartesianPart.map(cartesianPartTuple => // array --- новый массив из arrays для добавления в декартово произведение array.map(arrayElement => // cartesianPartTuple --- массив-префикс одного из элементов декартова произведения // arrayElement --- элемент одного из массива из arrays cartesianPartTuple.concat([arrayElement]) ) ) ), [[]] );
То же самое с использованием методов lodash
const cartesian = (...arrays) => _.reduce(arrays, (a, b) => _.flatten( _.map(a, ai => _.map(b, bi => ai.concat([bi]) ) ) ), [[]] );
Здесь методы JavaScript заменены на эквивалентные из lodash:
массив.map(маппер) ↔ _.map(массив, маппер) массив.reduce(редьюсер) ↔ _.reduce(массив, редьюсер) [].concat(...массив) ↔ _.flatten(массив)
Нерекурсивный способ с явным построением элемента декартова произведения по его номеру
function cartesian(...arrays) { // находим число элементов в декартовом произведении let resultLength = 1; for (let array of arrays) { resultLength *= array.length; }
// создаём массив такого размера и перебираем номер элемента let result = new Array(resultLength); for (let i = 0; i < resultLength; ++i) { // один элемент декартова произведения let element = new Array(arrays.length); let elementIndex = i; // цикл в обратном порядке нужен чтобы элементы начинали изменяться с конца for (let j = arrays.length - 1; j >= 0; --j) { const array = arrays[j]; // имеем биекцию между индексами элементов декартова произведения (числа от 0 до resultLength-1) // и кортежами длины arrays.length, в которых каждый элемент — индекс в соответствующем массиве element[j] = array[elementIndex % array.length]; // целочисленное деление elementIndex = Math.floor(elementIndex / array.length); } result[i] = element; } return result; }
Рекурсивный способ
С помощью рекурсии будут создаваться элементы декартова произведения: начиная с пустого массива на каждом шаге рекурсии перебираются все элементы текущего массива, создаётся копия набранного префикса элемента декартова произведения, к копии добавляется элемент массива и на полученном новом префиксе делается рекурсивный вызов.
function cartesian(...arrays) { let result = []; // функция, которая будет рекурсивно вызываться // глубина рекурсии равна arrays.length // в процессе рекурсии функция будет создавать часть элемента декартова произведения // в конце рекусрии функция добавит созданный элемент в массив result const recursion = (tuplePart) => { if (tuplePart.length === arrays.length) { result.push(tuplePart); } else { const array = arrays[tuplePart.length]; for (let element of array) { // создаём копию tuplePart и добавляем в неё очередной элемент const tuplePartWithNewElement = tuplePart.concat([element]); recursion(tuplePartWithNewElement); } } }; recursion([]); return result; }
Сниппет, в котором проверяется корректность работы всех предложенных способов
// cartesian 1 const f = (a, b) => [].concat(...a.map(ai => b.map(bi => ai.concat([bi])))); const cartesian1 = (...arrays) => arrays.reduce((a, b) => f(a, b), [[]]); // cartesian 2 const cartesian2 = (...arrays) => // итеративно получаем декартово произведение // нескольких первых массивов из arrays, // начиная с нуля массивов и пустого декартова произведения --- [[]] arrays.reduce((cartesianPart, array) => // сглаживание массива массивов [].concat(... // cartesianPart --- декартово произведение нескольких первых массивов из arrays cartesianPart.map(cartesianPartTuple => // array --- новый массив из arrays для добавления в декартово произведение array.map(arrayElement => // cartesianPartTuple --- массив-префикс одного из элементов декартова произведения // arrayElement --- элемент одного из массива из arrays cartesianPartTuple.concat([arrayElement]) ) ) ), [[]] ); // cartesian 3 const cartesian3 = (...arrays) => _.reduce(arrays, (a, b) => _.flatten( _.map(a, ai => _.map(b, bi => ai.concat([bi]) ) ) ), [[]] ); // cartesian 4 function cartesian4(...arrays) { // находим число элементов в декартовом произведении let resultLength = 1; for (let array of arrays) { resultLength *= array.length; } // создаём массив такого размера и перебираем номер элемента let result = new Array(resultLength); for (let i = 0; i < resultLength; ++i) { // один элемент декартова произведения let tuple = new Array(arrays.length); let tupleIndex = i; // цикл в обратном порядке нужен чтобы элементы начинали изменяться с конца for (let j = arrays.length - 1; j >= 0; --j) { const array = arrays[j]; // имеем биекцию между индексами элементов декартова произведения (числа от 0 до resultLength-1) // и кортежами длины arrays.length, в которых каждый элемент — индекс в соответствующем массиве tuple[j] = array[tupleIndex % array.length]; // целочисленное деление tupleIndex = Math.floor(tupleIndex / array.length); } result[i] = tuple; } return result; } // cartesian 5 function cartesian5(...arrays) { let result = []; // функция, которая будет рекурсивно вызываться // глубина рекурсии равна arrays.length // в процессе рекурсии функция будет создавать часть элемента декартова произведения // в конце рекусрии функция добавит созданный элемент в массив result const recursion = (tuplePart) => { if (tuplePart.length === arrays.length) { result.push(tuplePart); } else { const array = arrays[tuplePart.length]; for (let element of array) { // создаём копию tuplePart и добавляем в неё очередной элемент const tuplePartWithNewElement = tuplePart.concat([element]); recursion(tuplePartWithNewElement); } } }; recursion([]); return result; } // tests const cartesians = [ cartesian1, cartesian2, cartesian3, cartesian4, cartesian5 ]; const tests = [ { name: 'product of single array', input: [ [1, 2, 3] ], output: [ [1], [2], [3] ] }, { name: 'product of two arrays', input: [ [1, 2, 3], [10, 20] ], output: [ [1, 10], [1, 20], [2, 10], [2, 20], [3, 10], [3, 20] ] }, { name: 'product of three arrays', input: [ [1, 2], [10, 20], [100, 200, 300] ], output: [ [1, 10, 100], [1, 10, 200], [1, 10, 300], [1, 20, 100], [1, 20, 200], [1, 20, 300], [2, 10, 100], [2, 10, 200], [2, 10, 300], [2, 20, 100], [2, 20, 200], [2, 20, 300] ] }, { name: 'nested arrays', input: [ [[1], [2], [3]], [[10], [20]] ], output: [ [[1], [10]], [[1], [20]], [[2], [10]], [[2], [20]], [[3], [10]], [[3], [20]] ] } ]; console.log('если нет сообщений об ошибке, то все функции работают правильно'); cartesians.forEach((cartesian, index) => { for (let test of tests) { const output = cartesian(...test.input); const ok = _.isEqual(output, test.output); if (!ok) { console.log(`FAIL: cartesian function #${index + 1} for test ${test.name}`); console.log(` expected: ${JSON.stringify(test.output)}`); console.log(` received: ${JSON.stringify(output)}`); } } });
Замечание о пустом декартовом произведении
Практически все предложенные способы некорректно обрабатывают пустое декартово произведение, то есть вызов функции cartesian без аргументов. Декартово произведение нуля множеств равно пустому множеству, в нашем случае это пустой массив. При желании можно добавить проверку на это.
Готовые библиотечные реализации
В некоторых библиотеках существует функция декартова произведения:
js-combinatorics → cartesianProduct cartesian-product — npm, github d3-array → cross (только для двух массивов)