Solve this seemingly simple array loop puzzle in JavaScript

Question

For some reason, I'm having a hard time with this one. I like puzzles, but I'm not doing so well on this one.

The following array can have a large number of sets inside of it, but never deeper than what you see in this example (i.e., never deeper than 2 dimensions):

var list = [['a', 'b'], ['c'], ['d', 'e']];

With the above as input, how do I produce the following array in JavaScript?

[['a', 'c', 'd'], ['a', 'c', 'e'], ['b', 'c', 'd'], ['b', 'c', 'e']]

I'm sure the solution involves recursion, but it's not a simple tree structure, so it's not as simple as it looks.

Yeah. I tried recursion but it didn't work because it doesn't have a simple tree structure. It's more complicated than it looks. — jedmao, Jun 30 '13 at 21:27
@sfjedi it is indeed a problem that should be solved with recursion. You just need to figure out the induction step :-) — Pointy, Jun 30 '13 at 21:27
I would call this "cartesian product", and there's plenty of solutions to that problem in js. — goat, Jun 30 '13 at 21:40
@KarolyHorvath: You don't. Plain iteration can do this as well. — Bergi, Jun 30 '13 at 22:12
You don't "need" recursion, though it might be less code to write. Anything that can be written using recursion can be written as a sequential process. It might be more code (usually not much more), but it will run faster and use less memory. Which is better is up to you. — RobG, Jun 30 '13 at 22:45
@chris Thanks for pointing out it's a Cartesian product algorithm. That led me to the ultimate solution. — jedmao, Jun 30 '13 at 22:50
s/infinite/arbitrarily large amount/. (For one, Javascript doesn't support infinite lists, and I'm not sure this would be solvable even in a language that does. At least not meaningfully, since it would be the same as getting a list of the first elements of all the dimensions.) — millimoose, Jun 30 '13 at 22:54

Ry- · Accepted Answer · 2013-06-30T22:39:49.867

3

So you’re looking for ~~permutations~~ a Cartesian product?

function product(list) {
    // Keep a current index for each set
    var indices = list.map(_ => 0); // More Firefox 22 promotion :)
    indices[indices.length - 1] = -1;
    var result = [];

    while(true) {
        // Get the next permutation
        for(var i = indices.length - 1; i >= 0; i--) {
            if(++indices[i] === list[i].length) {
                indices[i] = 0;
            } else {
                break;
            }
        }

        if(i === -1) {
            // All done!
            return result;
        }

        // Turn the array of indices into an array of values
        result.push(indices.map((n, i) => list[i][n]));
    }
}

edited Jun 30 '13 at 22:39

answered Jun 30 '13 at 21:27

Ry-

218,210
55
464
476

1

Such a tease (with that FF-specific stuff) .. – user2246674 Jun 30 '13 at 21:29
It's OK. I'm using node, actually, so I have access to ES5 array extras. Let me try this out. – jedmao Jun 30 '13 at 21:30
1

This is a pretty clever way to do this, as it avoids the stack growth that a recursive version would experience. – Pointy Jun 30 '13 at 21:31
@sfjedi: This is rather an ES6 function extra. (There already!) On Node, use `list.map(function() { return 0; })` and `indices.map(function(n, i) { return list[i][n]; })`. – Ry- Jun 30 '13 at 21:31
@minitech this says ES5: http://dev.opera.com/articles/view/javascript-array-extras-in-detail/ – jedmao Jun 30 '13 at 21:51
@sfjedi: Not `map`, arrow function syntax. `_ => 0` as opposed to `function() { return 0; }`. – Ry- Jun 30 '13 at 22:01
@minitech Oh, fat arrow syntax. Reminds me of C#. – jedmao Jun 30 '13 at 22:02
You should not call this function [*permute*](http://en.wikipedia.org/wiki/Permutation), as that's not what it does. Call it *combinations* or *cartesian product* or something. – Bergi Jun 30 '13 at 22:18
@Bergi: It’s not one kind of [combination](https://en.wikipedia.org/wiki/Combination) either. I might call it Cartesian product once I find out what that is. Thanks :D – Ry- Jun 30 '13 at 22:20
Playing around with this solution, I see that there's one problem. The last array will always skip its first member on the first pass because you're incrementing immediately, and it hasn't had the benefit of having had its `0` index already processed like the arrays at the lower indices. Seems like you'd need to decrement the last index in your `indices` array before you begin. – Jun 30 '13 at 22:33
...one more potential problem is that if an empty array is included in the set, you'll have an infinite loop because of the preincrementing. Easy fix would be `>=` comparison to the `.length`... `++indices[i] >= list[i].length` – Jun 30 '13 at 22:35
@CrazyTrain: An empty array should never be included in the set. If that’s a possibility, I’d rather throw an error. And thanks for the fix! – Ry- Jun 30 '13 at 22:39
How would I convert this `list.map(_ => 0);` into non-FF code? I can convert the other fat arrows, but this one confuses me. – jedmao Jun 30 '13 at 22:53
@minitech: An empty array in the input list should just lead to an empty result, not throwing an exception. – Bergi Jun 30 '13 at 22:54
1

@sfjedi Guessing: `function(_) { return 0; }`. `_` is a convention stolen from other FP languages where it means "this argument is meant to be unused". I think either Haskell or Ocaml will actually throw an error if you have an unused argument not named `_`. – millimoose Jun 30 '13 at 22:59
@sfjedi: He showed you how a while ago. http://stackoverflow.com/questions/17394961/solve-this-seemingly-simple-array-loop-puzzle-in-javascript#comment25255601_17395021 – Jun 30 '13 at 23:06
@CrazyTrain thanks. @minitech I replaced the 2 FF functions and the following: `JSON.stringify(product([['a', 'b'], ['c'], ['d', 'e']]))` just returns `"[[null,null,null],[null,null,null],[null,null,null],[null,null,null]]"` – jedmao Jun 30 '13 at 23:12
@minitech http://jsfiddle.net/4wmS9/ look at the console – jedmao Jul 01 '13 at 02:35
@sfjedi: Your second `.map()` function doesn't have a `return` statement. – Jul 02 '13 at 02:58
@CrazyTrain sorry, stupid mistake. – jedmao Jul 03 '13 at 03:56
@minitech I just realized you're 15 years old. Bravo, Sir! – jedmao Jul 03 '13 at 03:58

score 1 · Answer 2 · answered Jun 30 '13 at 22:56

1

BTW, I'm using this to generate CSS selectors from a nested structure, like Sass. The following function works and is quite concise:

function cartesianProduct() {
    var result = this.selectors.reduce(function(a, b) {
        return a.map(function(x) {
            return b.map(function(y) {
                return [x, y].join(' ');
            });
        });
    })[0];
    return typeof result === 'string' ? result : result.join(', ');
}

answered Jun 30 '13 at 22:56

jedmao

10,224
11
59
65

*“I'm sure the solution involves recursion, but it's not a simple tree structure, so it's not as simple as it looks.”* A nested CSS structure is a tree :) – Ry- Jun 30 '13 at 23:15
What I mean is traversing through a tree is easy, but what we're doing here is much more than that. – jedmao Jul 01 '13 at 02:32

Solve this seemingly simple array loop puzzle in JavaScript

2 Answers2