Cartesian product of multiple arrays in JavaScript
Here is a functional solution to the problem (without any mutable variable!) using reduce
and flatten
, provided by 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>
How to implement cartesian product of n array with different lenghts in javascript?
The following works having n arrays:
function cartesianProduct(data) {
var current = [[]];
for (var p in data) {
var arr = data[p];
var newCurrent = [];
for (var c = 0; c < current.length; c++) {
var baseArray = current[c];
for (var a = 0; a < arr.length; a++) {
var clone = baseArray.slice();
clone.push(arr[a]);
newCurrent.push(clone);
}
}
current = newCurrent;
}
return current;
}
for the following data:
var data = {
size: ['s', 'm'],
color: ['blue', 'red'],
version: ['run', 'walk', 'jump']
};
will return all the combinations:
var variations = [
["s","blue","run"],
["s","blue","walk"],
["s","blue","jump"],
["s","red","run"],
["s","red","walk"],
["s","red","jump"],
["m","blue","run"],
["m","blue","walk"],
["m","blue","jump"],
["m","red","run"],
["m","red","walk"],
["m","red","jump"]
];
Cartesian product of 2 arrays
You don't need jquery for this:
var customerArray = [[10,'A'],[11,'B']];
var debtorArray = [[88,'W'],[99,'X']];
var customerDebtorMatrix = [];
for (var i = 0; i < customerArray.length; i++) {
for (var l = 0; l < debtorArray.length; l++) {
customerDebtorMatrix.push(customerArray[i].concat(debtorArray[l]));
}
}
customerDebtorMatrix
will be
[ [ 10, 'A', 88, 'W' ],
[ 10, 'A', 99, 'X' ],
[ 11, 'B', 88, 'W' ],
[ 11, 'B', 99, 'X' ] ]
Perfoming Cartesian product on arrays
One way to approach this problem is to continuously reduce the number of arrays one at a time by noting that
A0 × A1 × A2 = (A0 × A1) × A2
Consequently, you could write a function like this one, which computes the Cartesian product of two arrays:
int[] cartesianProduct(int[] one, int[] two) {
int[] result = new int[one.length * two.length];
int index = 0;
for (int v1: one) {
for (int v2: two) {
result[index] = v1 * v2;
index++;
}
}
return result;
}
Now, you can use this function to keep combining together pairs of arrays into one single array containing the overall Cartesian product. In pseudocode:
While there is more than one array left:
Remove two arrays.
Compute their Cartesian product.
Add that array back into the list.
Output the last array.
And, as actual Java:
Queue<int[]> worklist;
/* fill the worklist with your arrays; error if there are no arrays. */
while (worklist.size() > 1) {
int[] first = worklist.remove();
int[] second = worklist.remove();
worklist.add(cartesianProduct(first, second));
}
/* Obtain the result. */
int[] result = worklist.remove();
The problem with this approach is that it uses memory proportional to the total number of elements you produce. This can be a really huge number! If you just want to print all of the values out one at a time without storing them, there is a more efficient approach. The idea is that you can start listing off all possible combinations of indices in the different arrays, then just go multiply together the values at those positions. One way to do this is to maintain an "index array" saying what the next index to look at is. You can move from one index to the next by "incrementing" the array the same way you would increment a number. Here's some code for that:
int[] indexArray = new int[arrays.length];
mainLoop: while (true) {
/* Compute this entry. */
int result = 1;
for (int i = 0; i < arrays.length; i++) {
result *= arrays[i][indexArray[i]]
}
System.out.println(result);
/* Increment the index array. */
int index = 0;
while (true) {
/* See if we can bump this array index to the next value. If so, great!
* We're done.
*/
indexArray[index]++;
if (indexArray[index] < arrays[i].length) break;
/* Otherwise, overflow has occurred. If this is the very last array, we're
* done.
*/
indexArray[index] = 0;
index ++;
if (index == indexArray.length) break mainLoop;
}
}
This uses only O(L) memory, where L is the number of arrays you have, but produces potentially exponentially many values.
Hope this helps!
Cartesian product on multiple array of objects in javascript
Instead of using an array to push to, you want to merge the objects:
function cartesianProductOf() {
return Array.prototype.reduce.call(arguments, function(a, b) {
var ret = [];
a.forEach(function(a_el) {
b.forEach(function(b_el) {
ret.push(Object.assign({}, a_el, b_el));
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
});
});
return ret;
}, [{}]);
// ^^
}
If you don't want to use Object.assign
or it's polyfill, the equivalent would be
var r = {};
for (var p in a_el)
r[p] = a_el[p];
for (var p in b_el)
r[p] = b_el[p];
ret.push(r);
Cartesian Product of N arrays
this is called "cartesian product", php man page on arrays http://php.net/manual/en/ref.array.php shows some implementations (in comments).
and here's yet another one:
function array_cartesian() {
$_ = func_get_args();
if(count($_) == 0)
return array(array());
$a = array_shift($_);
$c = call_user_func_array(__FUNCTION__, $_);
$r = array();
foreach($a as $v)
foreach($c as $p)
$r[] = array_merge(array($v), $p);
return $r;
}
$cross = array_cartesian(
array('apples', 'pears', 'oranges'),
array('steve', 'bob')
);
print_r($cross);
Generation cartesian product objects from array values
First of all, that's not a problem with permutations
, it's exactly Cartesian product
.
In set
theory (and, usually, in other parts of mathematics), a Cartesian product
is a mathematical operation that returns a set
from multiple sets.
You can achieve that using ES6
features like map and reduce methods.
function cartesianProduct(...arrays) { return [...arrays].reduce((a, b) => a.map(x => b.map(y => x.concat(y))) .reduce((a, b) => a.concat(b), []), [[]]);}console.log(cartesianProduct([1, 2], [3, 4], [5, 6]));
Cartesian Product of multiple array
Thx for the help!
I add a valid answer with the implementation in java for the next guy, who has the same problem. I also do it generic so u can have any CartesianProduct on any Object, not just ints:
public class Product {
@SuppressWarnings("unchecked")
public static <T> List<T[]> getCartesianProduct(T[]... objects){
List<T[]> ret = null;
if (objects != null){
//saves length from first dimension. its the size of T[] of the returned list
int len = objects.length;
//saves all lengthes from second dimension
int[] lenghtes = new int[len];
// arrayIndex
int array = 0;
// saves the sum of returned T[]'s
int lenSum = 1;
for (T[] t: objects){
lenSum *= t.length;
lenghtes[array++] = t.length;
}
//initalize the List with the correct lenght to avoid internal array-copies
ret = new ArrayList<T[]>(lenSum);
//reusable class for instatiation of T[]
Class<T> clazz = (Class<T>) objects[0][0].getClass();
T[] tArray;
//values stores arrayIndexes to get correct values from objects
int[] values = new int[len];
for (int i = 0; i < lenSum; i++){
tArray = (T[])Array.newInstance(clazz, len);
for (int j = 0; j < len; j++){
tArray[j] = objects[j][values[j]];
}
ret.add(tArray);
//value counting:
//increment first value
values[0]++;
for (int v = 0; v < len; v++){
//check if values[v] doesn't exceed array length
if (values[v] == lenghtes[v]){
//set it to null and increment the next one, if not the last
values[v] = 0;
if (v+1 < len){
values[v+1]++;
}
}
}
}
}
return ret;
}
}
Related Topics
Incorrect Integer (2147483647) Is Inserted into MySQL
What Are Register_Globals in PHP
Run a PHP File in a Cron Job Using Cpanel
Get Everything Between ≪Tag≫ and ≪/Tag≫ With PHP
Lamp: How to Create .Zip of Large Files For the User on the Fly, Without Disk/Cpu Thrashing
Notice: Trying to Get Property of Non-Object Error
Insert String At Specified Position
PHP - Move a File into a Different Folder on the Server
$_Server['Http_Referer'] Missing
Send Array With Ajax to PHP Script
Is There a PHP Equivalent of Perl'S Www::Mechanize
How to Insert Element into Arrays At Specific Position
Converting Words to Numbers in PHP