iterate through all permutations of two variables

Question

I need to call the following function cross 4 times, for all permutations of the x and y variable with the values 1 and -1;

my approach:

var p = [-1, 1];

p.forEach(function(x) {
  p.forEach(function(y) {
    cross(x, y);
  });
});

Is there a shorter way of doing this?

I think there's an algorithm to produce n^2 combinations that is more efficient than n^2. — ssube, Jun 08 '15 at 16:52
By shorter do you mean in lines of code or in time (more efficient)? — Alvaro Montoro, Jun 08 '15 at 16:52
I think this question is better suited for [Code Review](http://codereview.stackexchange.com/), as finding all permutations of elements in Javascript arrays [already has an answer here](http://stackoverflow.com/questions/9960908/permutations-in-javascript). — alex, Jun 08 '15 at 16:55
@alex: In fact he's not looking for permutations, but for the [cartesian product](http://stackoverflow.com/q/15298912/1048572) of that array. — Bergi, Jun 08 '15 at 16:57
Are you looking for a general permutation/combination algorithm, either DFS or BFS? — Leo, Jun 08 '15 at 16:58
thats pretty fast. Running 1million time generally takes ~620ms. http://jsfiddle.net/1zbrshsd/ — Rooster, Jun 08 '15 at 16:59
for gereneric array cross product see: http://stackoverflow.com/q/12303989/1715004 — Filipe Borges, Jun 08 '15 at 17:00
@FilipeBorges good point. but my general point still holds true. its fast enough that the need for a faster solution is negligible. But its always fun to try to squeeze it out if you have the time available. :) — Rooster, Jun 08 '15 at 17:01
@alex This would likely be considered 'example code' and closed as off-topic on Code Review. — Simon Forsberg, Jun 08 '15 at 19:47
@SimonAndréForsberg +1 [fair enough](http://codereview.stackexchange.com/help/on-topic) — alex, Jun 08 '15 at 19:51

score 3 · Answer 1 · answered Jun 08 '15 at 16:59

If you want to be extra functional, you can use map and then reduce the arrays into one. I don't think it would necessarily be any more efficient than what you have now, nor is it much simpler (it is more functional, just slightly).

var d = [-1, 1];

var r = d.reduce(function(p, x) {
  return p.concat(d.map(function(y) {
    return cross(x, y);
  }));
}, []);

document.getElementById('r').textContent = JSON.stringify(r);

<pre id=r></pre>

I really don't think there is an algorithm with better than n^2 efficiency to produce n^2 combinations.

score 2 · Answer 2 · answered Jun 08 '15 at 16:58

2

Since you know the length of your array p you don't need a loop. The fastest solution would be:

var p = [-1, 1];
cross(p[0], p[0]);
cross(p[0], p[1]);
cross(p[1], p[0]);
cross(p[1], p[1]);

answered Jun 08 '15 at 16:58

bhspencer

13,086
5
35
44

2

this is the most obvious solution for the specific case, upvoted! – Filipe Borges Jun 08 '15 at 17:01
why are you using `0` instead of `-1`? – Mulan Jun 08 '15 at 17:03
@naomik: it's position 0, not value 0 – Brian Stephens Jun 08 '15 at 17:03
2

Hey, the array is static, so it would be even faster not accessing it at all and doing `cross(-1, -1); cross(-1, 1); cross(1, -1); cross(1, 1);` :-) – Bergi Jun 08 '15 at 17:25
That would be faster. – bhspencer Jun 08 '15 at 17:28

score 1 · Answer 3 · answered Jun 08 '15 at 16:56

There is some overhead in calling a function. e.g. putting the return pointer on the stack. It would probably be slightly faster to use two for loops rather than callbacks to forEach.

var p = [-1, 1];
for (var x = 0; x < p.length; x++) {
    for (var y = 0; y < p.length; y++) {
        cross(p[x], p[y]);
    } 
}

score 1 · Answer 4 · answered Jun 08 '15 at 17:03

1

This will be faster:

for (var n = 0; n < 4; ++n) 
     cross(n & 2 ? 1:-1, n & 1 ? -1:1);

but is it shorter?

answered Jun 08 '15 at 17:03

c-smile

26,734
7
59
86

iterate through all permutations of two variables

4 Answers4