How to get all combinations of unknown number of elements in unknown number of arrays?

Question

I thought about and searched for it a lot, and couldn't find an answer to this:

I need to write a js-function that gets an object with an unknown number of arrays, which again have an unknown number of elements. Like so:

{
    Color: ["Color : Red", "Color : Blue", "Color : Green"], 
    Size : ["Size : S", "Size : M", "Size : L"], 
    Material : ["Material : Cotton"], 
    Something : ["Something : Anything", "Something : Anotherthing"]
}

Again, this could be a whole lot more (or less) arrays and elements, but in this case I would want to achieve an output like this:

{0: "Color : Red > Size : S > Material : Cotton > Something : Anything",
 1: "Color : Red > Size : S > Material : Cotton > Something : Anotherthing",
 2: "Color : Red > Size : M > Material : Cotton > Something : Anything",
 3: "Color : Red > Size : M > Material : Cotton > Something : Anotherthing",
 4: "Color : Red > Size : L > Material : Cotton > Something : Anything",
 5: "Color : Red > Size : L > Material : Cotton > Something : Anotherthing",
 6: "Color : Blue > Size : S > Material : Cotton > Something : Anything",
 ...
 ...[and so forth... ]}

I tried to do a loop in a loop in a loop, but that failed. I then tried first finding the longest array, extracting it from the rest and then looping through every arrays for every element in the longest:

createMap = function(tagObj, longest){

  var longObj = tagObj[longest];
  var current = {};

  delete tagObj[longest];

  $.each(tagObj, function(name, obj){
    $.each(obj, function(index, tag){
      $.each(longObj, function(i, iniTag){
        if (current[i]!= undefined){
          current[i] += " > " + tag; 
        }
        else current[i] = iniTag + " > " + tag;
      })
    })
  })
  console.log(current);
}

But that just results in:

{0: "Color : Red, Size : S, Size : M, Size : L, .... "}

I hope I'm no just overlooking something really obvious - but I spent far too much time on it and just couldn't figure it out. And now I'm a nervous wreck and not able to think straight anymore. I would very much appreciate some help! Thanks in advance!

you shouldn't need to nest any deeper than 2 here. Loop over the object keys, and for each key, loop over it's value (which is an array.) — Kevin B, Feb 20 '14 at 16:30
A problem you're going to run into is that there is no guaranteed traversal order for the keys in your main object. That means you can't predict how the combined strings will look. The "Color" property *might* be first, or it might *not* be first. — Pointy, Feb 20 '14 at 16:31
Well, the initial order does not matter, but you're right, in the end, the outputs should all have the same order. I didn't even get there. Thx @Pointy for pointing it out! — stuckoverflow, Feb 20 '14 at 16:53
So you want to make a list of every possible combination. Is that right? That list might get very very long. — Seb, Feb 20 '14 at 16:56
@Seb It could get quite long, yes. But to be clear - I don't want to combine elements inside the same array! — stuckoverflow, Feb 20 '14 at 17:00
I'm not sure if this is possible in Javascript. But I guess you need to create a multi-dimensional array. Each color-value gets an child-array with each size, which gets a sub-array with each material, which gets a sub-array with each Something. Then you should be able to iterate over the multi-dimensional array in for-loops and create your output. — Seb, Feb 20 '14 at 17:05
Yes it is possible, also starting with object with N arrays. Do you accept answer in pseudocode? — Alberto, Feb 20 '14 at 17:08
possible duplicate of [JavaScript - Generating combinations from n arrays with m elements](http://stackoverflow.com/questions/15298912/javascript-generating-combinations-from-n-arrays-with-m-elements) — Bergi, Feb 20 '14 at 21:11

score 1 · Answer 1 · answered Feb 20 '14 at 17:43

You can use a simple recursive solution for this:

function combine( obj ) {
  var keys = Object.keys(obj), combinations = [];

  // keys.sort(); // optional

  function rc(ki, combo) {
    var list;

    if (ki === keys.length)
      combinations.push(combo);
    else {
      list = obj[ keys[ki] ];
      for (var i = 0; i < list.length; ++i)
        rc( ki + 1, combo + " " + list[i] );
    }
  }

  rc(0, '');
  return combinations;
}

That starts with a list of keys of the starting object, and an empty result array. Note that it might be wise to sort the keys so that the results are returned in a predictable order, since there's no defined ordering to the list of property names.

The recursive "rc" function starts with a particular index into the array of keys. For each string in the array associated with that key, the function calls itself recursively to operate on the next key, and a base string formed by appending the list element to the end of the string passed in. When the list of keys is exhausted, each completed combination string is appended to the result list.

The process is kicked of by invoking "rc" for the zeroth key, and an empty string as the start value.

Bali Balo · Answer 2 · 2014-02-20T19:53:48.273

You can do it with some kind of multiple counters: First by collecting every key and its number of elements, as well as a counter for every key.

As a numeral base (but with the base changing according to the number) we increment the lower one, and if this one reaches the max number allowed, we put it back to 0 and increment the next one etc. When every numbers have been incremented we have done a complete cycle through the elements.

function combinations(obj)
{
    var output = [];
    var meta = [], ml, cm;
    //ml: meta length
    //cm: current meta (in the while loop)

    for(var p in obj) if(obj.hasOwnProperty(p))
    {
        if(Object.prototype.toString.call(obj[p]) != '[object Array]')
            obj[p] = [obj[p]];
        meta.push({prop: p, len: obj[p].length, current: 0});
    }
    function addNow()
    {
        var add = {};
        for(var i = 0, l = meta.length; i < l; i++)
            add[meta[i].prop] = obj[meta[i].prop][meta[i].current]
        output.push(add);
    }
    cm = ml = meta.length - 1;
    while(cm >= 0)
    {
        addNow();
        cm = ml;
        while(cm >= 0 && ++meta[cm].current >= meta[cm].len)
        {
            meta[cm].current = 0;
            cm--;
        }
    }
    return output;
}

(See this fiddle)

How to get all combinations of unknown number of elements in unknown number of arrays?

2 Answers2