複数の配列のデカルト積を JavaScript でどのように実装しますか?
例として、
cartesian([1, 2], [10, 20], [100, 200, 300])
戻るべき
[
[1, 10, 100],
[1, 10, 200],
[1, 10, 300],
[2, 10, 100],
[2, 10, 200]
...
]
質問する
63545 次
35 に答える
90
これは、によって提供されるとを使用した、問題に対する機能的な解決策です (変更可能な変数はありません!) 。reduceflattenunderscore.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>備考: このソリューションはhttp://cwestblog.com/2011/05/02/cartesian-product-of-multiple-arrays/に触発されました
于 2012-09-27T19:33:36.693 に答える
55
ライブラリを使用せずに、プレーンな Javascript で @viebel のコードを修正したバージョンを次に示します。
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));于 2016-03-26T10:31:02.897 に答える
30
コミュニティは、これは些細なことであり、参照実装を簡単に見つけることができると考えているようです。しかし、簡単に調べてみると、1 つも見つかりませんでした…それか、単に車輪を再発明したり、教室のようなプログラミングの問題を解決したりするのが好きなだけなのかもしれません。いずれにせよ、あなたの幸運な日:
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]
]
比較的効率的な完全リファレンス実装…
効率性について: if をループから外して 2 つの別個のループを作成することで、いくつかの利点を得ることができます。これは、技術的には一定であり、分岐予測やすべての混乱を支援するためですが、その点は JavaScript では意味がありません。
于 2012-09-06T17:16:36.807 に答える
13
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]))));于 2016-08-24T00:22:50.637 に答える
9
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%; }以下は、古いブラウザと互換性のある同様のバージョンです。
function cartesianProduct(arrays) {
var result = [],
current = new Array(arrays.length);
(function backtracking(index) {
if(index == arrays.length) return result.push(current.slice());
for(var i=0; i<arrays[index].length; ++i) {
current[index] = arrays[index][i];
backtracking(index+1);
}
})(0);
return result;
}
cartesianProduct([[1,2],[10,20],[100,200,300]]).forEach(function(item) {
console.log('[' + item.join(', ') + ']');
});div.as-console-wrapper { max-height: 100%; }于 2015-04-12T03:50:32.250 に答える
4
reduce2D 配列を使用できます。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) =>
acc.flatMap(c => curr.map(n => [].concat(c, n)))
)
console.log(JSON.stringify(output))（これはニーナ・ショルツの答えに基づいています）
于 2019-08-21T18:40:50.103 に答える
3
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[][])
}
于 2019-03-05T11:04:41.217 に答える
1
製品を実際に結果セットに追加する前に、製品をフィルタリングおよび変更する機能を追加する非再帰的アプローチ。
注:.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;
}
于 2016-03-17T09:13:51.127 に答える
1
より読みやすい実装
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));于 2019-10-16T12:49:01.820 に答える