Как можно реализовать декартово произведение нескольких массивов в 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 (только для двух массивов)
