Как бы вы реализовали декартово произведение множественных массивов в JavaScript?
В качестве примера,
cartesian([1, 2], [10, 20], [100, 200, 300])
должен вернуться
[
[1, 10, 100],
[1, 10, 200],
[1, 10, 300],
[2, 10, 100],
[2, 10, 200]
...
]
Вот функциональное решение проблемы (без какой-либо изменяемой переменной !) С использованием 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>Все ответы здесь слишком сложны, большинство из них принимают 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 ] ]
Смотрите демонстрацию:
Синтаксис, который я использовал здесь, не является чем-то новым. В моем примере используются оператор спреда и остальные параметры - особенности JavaScript, определенные в 6-м выпуске стандарта ECMA-262, опубликованные в июне 2015 года и разработанные намного раньше, более известные как ES6 или ES2015. См:
Он делает такой код настолько простым, что грех не использовать его. Для старых платформ, которые не поддерживают его изначально, вы всегда можете использовать Babel или другие инструменты, чтобы преобразовать его в более старый синтаксис - и на самом деле мой пример, преданный Babel, все еще короче и проще, чем в большинстве примеров здесь, но он не действительно важно, потому что вывод транспиляции - это не то, что вам нужно понять или поддерживать, это просто факт, что я нашел интересным.
Нет необходимости писать сотни строк кода, которые трудно поддерживать, и нет необходимости использовать целые библиотеки для такой простой вещи, когда две линии ванильного JavaScript могут легко выполнить эту работу. Поскольку вы можете видеть, что действительно стоит использовать современные функции языка, и в тех случаях, когда вам необходимо поддерживать архаичные платформы без встроенной поддержки современных функций, вы всегда можете использовать Babel или другие инструменты для перевода нового синтаксиса на старый.
JavaScript развивается, и он делает это по какой-то причине. TC39 делает удивительную работу по разработке языка с добавлением новых функций, и разработчики браузеров делают удивительную работу по реализации этих функций.
Чтобы увидеть текущее состояние встроенной поддержки любой данной функции в браузерах, см.
Чтобы увидеть поддержку в версиях Node, см.
Чтобы использовать современный синтаксис на платформах, которые его не поддерживают, используйте Babel:
Вот модифицированная версия кода @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));кажется, что сообщество думает, что это тривиально и легко найти ссылочную реализацию, при кратковременном осмотре я не мог или, может быть, просто хотел, чтобы я изобретал колесо или решал проблемы с программированием как в классе ваш счастливый день:
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
Здесь необычное, простое рекурсивное решение:
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]]Следующая эффективная функция генератора возвращает декартово произведение всех заданных итераций:
// 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]));Используя типичную обратную трассировку с генераторами 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%; }Вот рекурсивный способ использования функции генератора 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]))));Это чистое решение 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)));Версия coffeescript с lodash:
_ = require("lodash")
cartesianProduct = ->
return _.reduceRight(arguments, (a,b) ->
_.flatten(_.map(a,(x) -> _.map b, (y) -> x.concat(y)), true)
, [ [] ])
Однострочный подход для лучшего чтения с отступами.
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; }Это помечено как функциональное программирование, поэтому давайте взглянем на монаду 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]))Несколько ответов в этом разделе терпят неудачу, если какой-либо из входных массивов содержит элемент массива. Вам лучше проверить это.
В любом случае нет необходимости подчеркивать, 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))); Для тех, кому нужен 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[][])
}
В моей конкретной ситуации "старомодный" подход казался более эффективным, чем методы, основанные на более современных функциях. Ниже приведен код (в том числе небольшое сравнение с другими решениями, размещенными в этом потоке 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
Нерекурсивный подход, который добавляет возможность фильтровать и модифицировать продукты, прежде чем добавлять их в результирующий набор. Обратите внимание на использование .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;
}
Просто для выбора простая простая реализация с использованием массива 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))), []);
Простая, модифицированная версия кода @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 ] ];
*/
Современный 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')
);Вы можете 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))Я заметил, что никто не опубликовал решение, позволяющее передавать функцию для обработки каждой комбинации, поэтому вот мое решение:
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?
Обычный метод 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]
]);
Простой "разум и визуально дружественное" решение.
// 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']
));
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>Еще одна реализация. Не самый короткий или причудливый, но быстрый:
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;
}
Требуются функции стрелки, хотя и, вероятно, не так эффективно. :/
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]))Для записи
Здесь идет моя версия этого. Я сделал это с помощью простейшего итератора 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;
}
С наилучшими пожеланиями.
Более читаемая реализация
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));