Декартово произведение множества массивов в JavaScript
Как бы вы реализовали декартово произведение множественных массивов в JavaScript?
В качестве примера,
cartesian([1, 2], [10, 20], [100, 200, 300])
должен вернуться
[
[1, 10, 100],
[1, 10, 200],
[1, 10, 300],
[2, 10, 100],
[2, 10, 200]
...
]
Ответы
Ответ 1
Вот функциональное решение проблемы (без какой-либо изменяемой переменной !) С использованием reduce и flatten, предоставленное underscore.js:
function cartesianProductOf() {
return _.reduce(arguments, function(a, b) {
return _.flatten(_.map(a, function(x) {
return _.map(b, function(y) {
return x.concat([y]);
});
}), true);
}, [ [] ]);
}
// [[1,3,"a"],[1,3,"b"],[1,4,"a"],[1,4,"b"],[2,3,"a"],[2,3,"b"],[2,4,"a"],[2,4,"b"]]
console.log(cartesianProductOf([1, 2], [3, 4], ['a']));
<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.9.1/underscore.js"></script>
Ответ 2
2017 Обновление: 2-строчный ответ с ванилью JS
Все ответы здесь слишком сложны, большинство из них принимают 20 строк кода или даже больше.
В этом примере используется только две строки ванильного JavaScript, без lodash, underscore и других библиотек:
let f = (a, b) => [].concat(...a.map(a => b.map(b => [].concat(a, b))));
let cartesian = (a, b, ...c) => b ? cartesian(f(a, b), ...c) : a;
Обновление:
Это то же самое, что и выше, но улучшено, чтобы строго следовать Руководство по стилю JavaScript для Airbnb - проверено с помощью ESLint с eslint-config-airbnb-base:
const f = (a, b) => [].concat(...a.map(d => b.map(e => [].concat(d, e))));
const cartesian = (a, b, ...c) => (b ? cartesian(f(a, b), ...c) : a);
Особая благодарность ZuBB за то, что она сообщила мне о проблемах с линкером с исходным кодом.
Пример
Это точный пример из вашего вопроса:
let output = cartesian([1,2],[10,20],[100,200,300]);
Выход
Это вывод этой команды:
[ [ 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 ] ]
Demo
Смотрите демонстрацию:
Синтаксис
Синтаксис, который я использовал здесь, не является чем-то новым.
В моем примере используются оператор спреда и остальные параметры - особенности JavaScript, определенные в 6-м выпуске стандарта ECMA-262, опубликованные в июне 2015 года и разработанные намного раньше, более известные как ES6 или ES2015. См:
Он делает такой код настолько простым, что грех не использовать его. Для старых платформ, которые не поддерживают его изначально, вы всегда можете использовать Babel или другие инструменты, чтобы преобразовать его в более старый синтаксис - и на самом деле мой пример, преданный Babel, все еще короче и проще, чем в большинстве примеров здесь, но он не действительно важно, потому что вывод транспиляции - это не то, что вам нужно понять или поддерживать, это просто факт, что я нашел интересным.
Заключение
Нет необходимости писать сотни строк кода, которые трудно поддерживать, и нет необходимости использовать целые библиотеки для такой простой вещи, когда две линии ванильного JavaScript могут легко выполнить эту работу. Поскольку вы можете видеть, что действительно стоит использовать современные функции языка, и в тех случаях, когда вам необходимо поддерживать архаичные платформы без встроенной поддержки современных функций, вы всегда можете использовать Babel или другие инструменты для перевода нового синтаксиса на старый.
Не используйте код 1995
JavaScript развивается, и он делает это по какой-то причине. TC39 делает удивительную работу по разработке языка с добавлением новых функций, и разработчики браузеров делают удивительную работу по реализации этих функций.
Чтобы увидеть текущее состояние встроенной поддержки любой данной функции в браузерах, см.
Чтобы увидеть поддержку в версиях Node, см.
Чтобы использовать современный синтаксис на платформах, которые его не поддерживают, используйте Babel:
Ответ 3
Вот модифицированная версия кода @viebel в простом Javascript, без использования какой-либо библиотеки:
function cartesianProduct(arr) {
return arr.reduce(function(a,b){
return a.map(function(x){
return b.map(function(y){
return x.concat(y);
})
}).reduce(function(a,b){ return a.concat(b) },[])
}, [[]])
}
var a = cartesianProduct([[1, 2,3], [4, 5,6], [7, 8], [9,10]]);
console.log(JSON.stringify(a));
Ответ 4
кажется, что сообщество думает, что это тривиально и легко найти ссылочную реализацию, при кратковременном осмотре я не мог или, может быть, просто хотел, чтобы я изобретал колесо или решал проблемы с программированием как в классе ваш счастливый день:
function cartProd(paramArray) {
function addTo(curr, args) {
var i, copy,
rest = args.slice(1),
last = !rest.length,
result = [];
for (i = 0; i < args[0].length; i++) {
copy = curr.slice();
copy.push(args[0][i]);
if (last) {
result.push(copy);
} else {
result = result.concat(addTo(copy, rest));
}
}
return result;
}
return addTo([], Array.prototype.slice.call(arguments));
}
>> console.log(cartProd([1,2], [10,20], [100,200,300]));
>> [
[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]
]
полная эталонная реализация, которая относительно эффективна...:-D
по эффективности: вы могли бы получить некоторые, взяв if из цикла и имея 2 отдельных цикла, поскольку он технически постоянный, и вы будете помогать с предсказанием ветвления и всем этим беспорядком, но этот момент является спорным в Javascript
anywho, наслаждайтесь -ck
Ответ 5
Здесь необычное, простое рекурсивное решение:
function cartesianProduct(a) { // a = array of array
var i, j, l, m, a1, o = [];
if (!a || a.length == 0) return a;
a1 = a.splice(0, 1)[0]; // the first array of a
a = cartesianProduct(a);
for (i = 0, l = a1.length; i < l; i++) {
if (a && a.length) for (j = 0, m = a.length; j < m; j++)
o.push([a1[i]].concat(a[j]));
else
o.push([a1[i]]);
}
return o;
}
console.log(cartesianProduct([[1,2], [10,20], [100,200,300]]));
// [[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]]
Ответ 6
Следующая эффективная функция генератора возвращает декартово произведение всех заданных итераций:
// Generate cartesian product of given iterables:
function* cartesian(head, ...tail) {
const remainder = tail.length > 0 ? cartesian(...tail) : [[]];
for (let r of remainder) for (let h of head) yield [h, ...r];
}
// Example:
console.log(...cartesian([1, 2], [10, 20], [100, 200, 300]));
Ответ 7
Используя типичную обратную трассировку с генераторами ES6,
function cartesianProduct(...arrays) {
let current = new Array(arrays.length);
return (function* backtracking(index) {
if(index == arrays.length) yield current.slice();
else for(let num of arrays[index]) {
current[index] = num;
yield* backtracking(index+1);
}
})(0);
}
for (let item of cartesianProduct([1,2],[10,20],[100,200,300])) {
console.log('[' + item.join(', ') + ']');
}
div.as-console-wrapper { max-height: 100%; }
Ответ 8
Вот рекурсивный способ использования функции генератора ECMAScript 2015 , поэтому вам не нужно сразу создавать все кортежи:
function* cartesian() {
let arrays = arguments;
function* doCartesian(i, prod) {
if (i == arrays.length) {
yield prod;
} else {
for (let j = 0; j < arrays[i].length; j++) {
yield* doCartesian(i + 1, prod.concat([arrays[i][j]]));
}
}
}
yield* doCartesian(0, []);
}
console.log(JSON.stringify(Array.from(cartesian([1,2],[10,20],[100,200,300]))));
console.log(JSON.stringify(Array.from(cartesian([[1],[2]],[10,20],[100,200,300]))));
Ответ 9
Это чистое решение ES6, используя функции стрелок
function cartesianProduct(arr) {
return arr.reduce((a, b) =>
a.map(x => b.map(y => x.concat(y)))
.reduce((a, b) => a.concat(b), []), [[]]);
}
var arr = [[1, 2], [10, 20], [100, 200, 300]];
console.log(JSON.stringify(cartesianProduct(arr)));
Ответ 10
Версия coffeescript с lodash:
_ = require("lodash")
cartesianProduct = ->
return _.reduceRight(arguments, (a,b) ->
_.flatten(_.map(a,(x) -> _.map b, (y) -> x.concat(y)), true)
, [ [] ])
Ответ 11
Однострочный подход для лучшего чтения с отступами.
result = data.reduce(
(a, b) => a.reduce(
(r, v) => r.concat(b.map(w => [].concat(v, w))),
[]
)
);
Требуется один массив с массивами разыскиваемых декартовых элементов.
var data = [[1, 2], [10, 20], [100, 200, 300]],
result = data.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; }
Ответ 12
Это помечено как функциональное программирование, поэтому давайте взглянем на монаду List:
Одно из приложений для этого монадического списка представляет недетерминированные вычисления. List может содержать результаты для всех путей выполнения в алгоритме...
Ну, это звучит как идеально подходит для cartesian. JavaScript дает нам Array а функция монадического связывания - Array.prototype.flatMap, поэтому позвольте использовать их -
const cartesian = (...all) =>
{ const loop = (t, a, ...more) =>
a === undefined
? [ t ]
: a .flatMap (x => loop ([ ...t, x ], ...more))
return loop ([], ...all)
}
console .log (cartesian ([1,2], [10,20], [100,200,300]))
Ответ 13
Несколько ответов в этом разделе терпят неудачу, если какой-либо из входных массивов содержит элемент массива. Вам лучше проверить это.
В любом случае нет необходимости подчеркивать, lodash вообще. Я считаю, что это нужно делать с чистым JS ES6, насколько это возможно.
Этот фрагмент кода использует сокращение и вложенную карту, просто чтобы получить декартово произведение двух массивов, однако второй массив происходит от рекурсивного вызова к той же функции с одним меньшим массивом; следовательно. a[0].cartesian(...a.slice(1))
Array.prototype.cartesian = function(...a){
return a.length ? this.reduce((p,c) => (p.push(...a[0].cartesian(...a.slice(1)).map(e => a.length > 1 ? [c,...e] : [c,e])),p),[])
: this;
};
var arr = ['a', 'b', 'c'],
brr = [1,2,3],
crr = [[9],[8],[7]];
console.log(JSON.stringify(arr.cartesian(brr,crr)));
Ответ 14
Для тех, кому нужен TypeScript (переопределён ответ @Danny)
/**
* Calculates "Cartesian Product" sets.
* @example
* cartesianProduct([[1,2], [4,8], [16,32]])
* Returns:
* [
* [1, 4, 16],
* [1, 4, 32],
* [1, 8, 16],
* [1, 8, 32],
* [2, 4, 16],
* [2, 4, 32],
* [2, 8, 16],
* [2, 8, 32]
* ]
* @see https://stackoverflow.com/a/36234242/1955709
* @see https://en.wikipedia.org/wiki/Cartesian_product
* @param arr {T[][]}
* @returns {T[][]}
*/
function cartesianProduct<T> (arr: T[][]): T[][] {
return arr.reduce((a, b) => {
return a.map(x => {
return b.map(y => {
return x.concat(y)
})
}).reduce((c, d) => c.concat(d), [])
}, [[]] as T[][])
}
Ответ 15
В моей конкретной ситуации "старомодный" подход казался более эффективным, чем методы, основанные на более современных функциях. Ниже приведен код (в том числе небольшое сравнение с другими решениями, размещенными в этом потоке by @rsp и @sebnukem), если он окажется полезным и для кого-то другого.
Идея следующая. Скажем, мы строим внешнее произведение массивов N, a_1,...,a_N, каждый из которых имеет компоненты m_i. Внешнее произведение этих массивов имеет элементы M=m_1*m_2*...*m_N, и мы можем идентифицировать каждый из них с вектором размерности N-, компоненты которого являются положительными целыми числами, а i -й компонент строго ограничен сверху на m_i. Например, вектор (0, 0, ..., 0) будет соответствовать конкретной комбинации, в которой один берет первый элемент из каждого массива, тогда как (m_1-1, m_2-1, ..., m_N-1) идентифицируется с комбинацией, в которой каждый берет последний элемент из каждого массива. Таким образом, для построения всех комбинаций M функция ниже последовательно конструирует все такие векторы и для каждого из них идентифицирует соответствующую комбинацию элементов входных массивов.
function cartesianProduct(){
const N = arguments.length;
var arr_lengths = Array(N);
var digits = Array(N);
var num_tot = 1;
for(var i = 0; i < N; ++i){
const len = arguments[i].length;
if(!len){
num_tot = 0;
break;
}
digits[i] = 0;
num_tot *= (arr_lengths[i] = len);
}
var ret = Array(num_tot);
for(var num = 0; num < num_tot; ++num){
var item = Array(N);
for(var j = 0; j < N; ++j){ item[j] = arguments[j][digits[j]]; }
ret[num] = item;
for(var idx = 0; idx < N; ++idx){
if(digits[idx] == arr_lengths[idx]-1){
digits[idx] = 0;
}else{
digits[idx] += 1;
break;
}
}
}
return ret;
}
//------------------------------------------------------------------------------
let _f = (a, b) => [].concat(...a.map(a => b.map(b => [].concat(a, b))));
let cartesianProduct_rsp = (a, b, ...c) => b ? cartesianProduct_rsp(_f(a, b), ...c) : a;
//------------------------------------------------------------------------------
function cartesianProduct_sebnukem(a) {
var i, j, l, m, a1, o = [];
if (!a || a.length == 0) return a;
a1 = a.splice(0, 1)[0];
a = cartesianProduct_sebnukem(a);
for (i = 0, l = a1.length; i < l; i++) {
if (a && a.length) for (j = 0, m = a.length; j < m; j++)
o.push([a1[i]].concat(a[j]));
else
o.push([a1[i]]);
}
return o;
}
//------------------------------------------------------------------------------
const L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
const args = [L, L, L, L, L, L];
let fns = {
'cartesianProduct': function(args){ return cartesianProduct(...args); },
'cartesianProduct_rsp': function(args){ return cartesianProduct_rsp(...args); },
'cartesianProduct_sebnukem': function(args){ return cartesianProduct_sebnukem(args); }
};
Object.keys(fns).forEach(fname => {
console.time(fname);
const ret = fns[fname](args);
console.timeEnd(fname);
});
с node v6.12.2, я получаю следующие тайминги:
cartesianProduct: 427.378ms
cartesianProduct_rsp: 1710.829ms
cartesianProduct_sebnukem: 593.351ms
Ответ 16
Нерекурсивный подход, который добавляет возможность фильтровать и модифицировать продукты, прежде чем добавлять их в результирующий набор. Обратите внимание на использование .map, а не .forEach. В некоторых браузерах .map работает быстрее.
function crossproduct(arrays,rowtest,rowaction) {
// Calculate the number of elements needed in the result
var result_elems = 1, row_size = arrays.length;
arrays.map(function(array) {
result_elems *= array.length;
});
var temp = new Array(result_elems), result = [];
// Go through each array and add the appropriate element to each element of the temp
var scale_factor = result_elems;
arrays.map(function(array)
{
var set_elems = array.length;
scale_factor /= set_elems;
for(var i=result_elems-1;i>=0;i--) {
temp[i] = (temp[i] ? temp[i] : []);
var pos = i / scale_factor % set_elems;
// deal with floating point results for indexes, this took a little experimenting
if(pos < 1 || pos % 1 <= .5) {
pos = Math.floor(pos);
} else {
pos = Math.min(array.length-1,Math.ceil(pos));
}
temp[i].push(array[pos]);
if(temp[i].length===row_size) {
var pass = (rowtest ? rowtest(temp[i]) : true);
if(pass) {
if(rowaction) {
result.push(rowaction(temp[i]));
} else {
result.push(temp[i]);
}
}
}
}
});
return result;
}
Ответ 17
Просто для выбора простая простая реализация с использованием массива reduce:
const array1 = ["day", "month", "year", "time"];
const array2 = ["from", "to"];
const process = (one, two) => [one, two].join(" ");
const product = array1.reduce((result, one) => result.concat(array2.map(two => process(one, two))), []);
Ответ 18
Простая, модифицированная версия кода @viebel в простом Javascript:
function cartesianProduct(...arrays) {
return arrays.reduce((a, b) => {
return [].concat(...a.map(x => {
const next = Array.isArray(x) ? x : [x];
return [].concat(b.map(y => next.concat(...[y])));
}));
});
}
const product = cartesianProduct([1, 2], [10, 20], [100, 200, 300]);
console.log(product);
/*
[ [ 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 ] ];
*/
Ответ 19
Современный JavaScript всего за несколько строк. Никаких внешних библиотек или зависимостей, таких как Lodash.
function cartesian(...arrays) {
return arrays.reduce((a, b) => a.flatMap(x => b.map(y => x.concat([y]))), [ [] ]);
}
console.log(
cartesian([1, 2], [10, 20], [100, 200, 300])
.map(arr => JSON.stringify(arr))
.join('\n')
);
Ответ 20
Вы можете reduce 2D-массив. Используйте flatMap на массиве аккумуляторов, чтобы получить acc.length x curr.length количество комбинаций в каждом цикле. [].concat(c, n) используется потому, что c - это число в первой итерации, а затем массив.
const data = [ [1, 2], [10, 20], [100, 200, 300] ];
const output = data.reduce((acc, curr, i) =>
acc.flatMap(c => curr.map(n => [].concat(c, n)))
)
console.log(JSON.stringify(output))
Ответ 21
Я заметил, что никто не опубликовал решение, позволяющее передавать функцию для обработки каждой комбинации, поэтому вот мое решение:
const _ = require('lodash')
function combinations(arr, f, xArr = []) {
return arr.length>1
? _.flatMap(arr[0], x => combinations(arr.slice(1), f, xArr.concat(x)))
: arr[0].map(x => f(...xArr.concat(x)))
}
// use case
const greetings = ["Hello", "Goodbye"]
const places = ["World", "Planet"]
const punctuationMarks = ["!", "?"]
combinations([greetings,places,punctuationMarks], (greeting, place, punctuationMark) => `${greeting} ${place}${punctuationMark}`)
.forEach(row => console.log(row))
Вывод:
Hello World!
Hello World?
Hello Planet!
Hello Planet?
Goodbye World!
Goodbye World?
Goodbye Planet!
Goodbye Planet?
Ответ 22
Обычный метод JS-перебора, который принимает массив массивов в качестве входных данных.
var cartesian = function(arrays) {
var product = [];
var precals = [];
var length = arrays.reduce(function(acc, curr) {
return acc * curr.length
}, 1);
for (var i = 0; i < arrays.length; i++) {
var array = arrays[i];
var mod = array.length;
var div = i > 0 ? precals[i - 1].div * precals[i - 1].mod : 1;
precals.push({
div: div,
mod: mod
});
}
for (var j = 0; j < length; j++) {
var item = [];
for (var i = 0; i < arrays.length; i++) {
var array = arrays[i];
var precal = precals[i];
var k = (~~(j / precal.div)) % precal.mod;
item.push(array[k]);
}
product.push(item);
}
return product;
};
cartesian([
[1],
[2, 3]
]);
cartesian([
[1],
[2, 3],
[4, 5, 6]
]);
Ответ 23
Простой "разум и визуально дружественное" решение.
![введите описание изображения здесь]()
// t = [i, length]
const moveThreadForwardAt = (t, tCursor) => {
if (tCursor < 0)
return true; // reached end of first array
const newIndex = (t[tCursor][0] + 1) % t[tCursor][1];
t[tCursor][0] = newIndex;
if (newIndex == 0)
return moveThreadForwardAt(t, tCursor - 1);
return false;
}
const cartesianMult = (...args) => {
let result = [];
const t = Array.from(Array(args.length)).map((x, i) => [0, args[i].length]);
let reachedEndOfFirstArray = false;
while (false == reachedEndOfFirstArray) {
result.push(t.map((v, i) => args[i][v[0]]));
reachedEndOfFirstArray = moveThreadForwardAt(t, args.length - 1);
}
return result;
}
// cartesianMult(
// ['a1', 'b1', 'c1'],
// ['a2', 'b2'],
// ['a3', 'b3', 'c3'],
// ['a4', 'b4']
// );
console.log(cartesianMult(
['a1'],
['a2', 'b2'],
['a3', 'b3']
));
Ответ 24
var chars = ['A', 'B', 'C']
var nums = [1, 2, 3]
var cartesianProduct = function() {
return _.reduce(arguments, function(a, b) {
return _.flatten(_.map(a, function(x) {
return _.map(b, function(y) {
return x.concat(y);
});
}), true);
}, [
[]
]);
};
console.log(cartesianProduct(chars, nums))
<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore-min.js"></script>
Ответ 25
Еще одна реализация. Не самый короткий или причудливый, но быстрый:
function cartesianProduct() {
var arr = [].slice.call(arguments),
intLength = arr.length,
arrHelper = [1],
arrToReturn = [];
for (var i = arr.length - 1; i >= 0; i--) {
arrHelper.unshift(arrHelper[0] * arr[i].length);
}
for (var i = 0, l = arrHelper[0]; i < l; i++) {
arrToReturn.push([]);
for (var j = 0; j < intLength; j++) {
arrToReturn[i].push(arr[j][(i / arrHelper[j + 1] | 0) % arr[j].length]);
}
}
return arrToReturn;
}
Ответ 26
Библиотеки не нужны! :)
Требуются функции стрелки, хотя и, вероятно, не так эффективно. :/
const flatten = (xs) =>
xs.flat(Infinity)
const binaryCartesianProduct = (xs, ys) =>
xs.map((xi) => ys.map((yi) => [xi, yi])).flat()
const cartesianProduct = (...xss) =>
xss.reduce(binaryCartesianProduct, [[]]).map(flatten)
console.log(cartesianProduct([1,2,3], [1,2,3], [1,2,3]))
Ответ 27
Для записи
Здесь идет моя версия этого. Я сделал это с помощью простейшего итератора javascript "for()", поэтому он совместим в любом случае и имеет лучшую производительность.
function cartesian(arrays){
var quant = 1, counters = [], retArr = [];
// Counts total possibilities and build the counters Array;
for(var i=0;i<arrays.length;i++){
counters[i] = 0;
quant *= arrays[i].length;
}
// iterate all possibilities
for(var i=0,nRow;i<quant;i++){
nRow = [];
for(var j=0;j<counters.length;j++){
if(counters[j] < arrays[j].length){
nRow.push(arrays[j][counters[j]]);
} else { // in case there is no such an element it restarts the current counter
counters[j] = 0;
nRow.push(arrays[j][counters[j]]);
}
counters[j]++;
}
retArr.push(nRow);
}
return retArr;
}
С наилучшими пожеланиями.
Ответ 28
Более читаемая реализация
function productOfTwo(one, two) {
return one.flatMap(x => two.map(y => [].concat(x, y)));
}
function product(head = [], ...tail) {
if (tail.length === 0) return head;
return productOfTwo(head, product(...tail));
}
const test = product(
[1, 2, 3],
['a', 'b']
);
console.log(JSON.stringify(test));
