Variable amount of nested for loops

Question

Edit: I'm sorry, but I forgot to mention that I'll need the values of the counter variables. So making one loop isn't a solution I'm afraid.

I'm not sure if this is possible at all, but I would like to do the following. To a function, an array of numbers is passed. Each number is the upper limit of a for loop, for example, if the array is [2, 3, 5], the following code should be executed:

for(var a = 0; a < 2; a++) {
     for(var b = 0; b < 3; b++) {
          for(var c = 0; c < 5; c++) {
                doSomething([a, b, c]);
          }
     }
}

So the amount of nested for loops is equal to the length of the array. Would there be any way to make this work? I was thinking of creating a piece of code which adds each for loop to a string, and then evaluates it through eval. I've read however that eval should not be one's first choice as it can have dangerous results too.

What technique might be appropriate here?

Answer 1

Recursion is overkill here. You can use generators:

function* allPossibleCombinations(lengths) {
  const n = lengths.length;

  let indices = [];
  for (let i = n; --i >= 0;) {
    if (lengths[i] === 0) { return; }
    if (lengths[i] !== (lengths[i] & 0x7fffffff)) { throw new Error(); }
    indices[i] = 0;
  }

  while (true) {
    yield indices;
    // Increment indices.
    ++indices[n - 1];
    for (let j = n; --j >= 0 && indices[j] === lengths[j];) {
      if (j === 0) { return; }
      indices[j] = 0;
      ++indices[j - 1];
    }
  }
}

for ([a, b, c] of allPossibleCombinations([3, 2, 2])) {
  console.log(`${a}, ${b}, ${c}`);
}

The intuition here is that we keep a list of indices that are always less than the corresponding length.

The second loop handles carry. As when incrementing a decimal number 199, we go to (1, 9, 10), and then carry to get (1, 10, 0) and finally (2, 0, 0). If we don't have enough digits to carry into, we're done.

Answer 2

One could also use a generator for that:

  function loop(...times) {
    function* looper(times, prev = []) {
       if(!times.length) {
           yield prev;
           return;
       }
       const [max, ...rest] = times;
       for(let current = 0; current < max; current++) {
         yield* looper(rest, [...prev, current]);
       }
   }
   return looper(times);
 }

That can then be used as:

  for(const [j, k, l, m] of loop(1, 2, 3, 4)) {
     //...
  }

Answer 3

This is my attempt at simplifying the non-recursive solution by Mike Samuel. I also add the ability to set a range (not just maximum) for every integer argument.

function everyPermutation(args, fn) {
    var indices = args.map(a => a.min);

    for (var j = args.length; j >= 0;) {
        fn.apply(null, indices);

        // go through indices from right to left setting them to 0
        for (j = args.length; j--;) {
            // until we find the last index not at max which we increment
            if (indices[j] < args[j].max) {
                ++indices[j];
                break;
            }
            indices[j] = args[j].min;
        }
    }
}

everyPermutation([
    {min:4, max:6},
    {min:2, max:3},
    {min:0, max:1}
], function(a, b, c) {
    console.log(a + ',' + b + ',' + c);
});

Answer 4

You can use the greedy algorithm to enumerate all elements of the cartesian product 0:2 x 0:3 x 0:5. This algorithm is performed by my function greedy_backward below. I am not an expert in Javascript and maybe this function could be improved.

function greedy_backward(sizes, n) {
  for (var G = [1], i = 0; i<sizes.length; i++) G[i+1] = G[i] * sizes[i]; 
  if (n>=_.last(G)) throw new Error("n must be <" + _.last(G));
  for (i = 0; i<sizes.length; i++) if (sizes[i]!=parseInt(sizes[i]) || sizes[i]<1){  throw new Error("sizes must be a vector of integers be >1"); }; 
  for (var epsilon=[], i=0; i < sizes.length; i++) epsilon[i]=0;
  while(n > 0){
    var k = _.findIndex(G, function(x){ return n < x; }) - 1;
    var e = (n/G[k])>>0;
    epsilon[k] = e;
    n = n-e*G[k];
  }
  return epsilon;
}

It enumerates the elements of the Cartesian product in the anti-lexicographic order (you will see the full enumeration in the doSomething example):

~ var sizes = [2, 3, 5];
~ greedy_backward(sizes,0);
0,0,0
~ greedy_backward(sizes,1);
1,0,0
~ greedy_backward(sizes,2);
0,1,0
~ greedy_backward(sizes,3);
1,1,0
~ greedy_backward(sizes,4);
0,2,0
~ greedy_backward(sizes,5);
1,2,0

This is a generalization of the binary representation (the case when sizes=[2,2,2,...]).

Example:

~ function doSomething(v){
    for (var message = v[0], i = 1; i<v.length; i++) message = message + '-' + v[i].toString(); 
    console.log(message); 
  }
~ doSomething(["a","b","c"])
a-b-c
~ for (var max = [1], i = 0; i<sizes.length; i++) max = max * sizes[i]; 
30
~ for(i=0; i<max; i++){
    doSomething(greedy_backward(sizes,i));
  }
0-0-0
1-0-0
0-1-0
1-1-0
0-2-0
1-2-0
0-0-1
1-0-1
0-1-1
1-1-1
0-2-1
1-2-1
0-0-2
1-0-2
0-1-2
1-1-2
0-2-2
1-2-2
0-0-3
1-0-3
0-1-3
1-1-3
0-2-3
1-2-3
0-0-4
1-0-4
0-1-4
1-1-4
0-2-4
1-2-4

If needed, the reverse operation is simple:

function greedy_forward(sizes, epsilon) {
  if (sizes.length!=epsilon.length) throw new Error("sizes and epsilon must have the same length");
  for (i = 0; i<sizes.length; i++) if (epsilon[i] <0 || epsilon[i] >= sizes[i]){  throw new Error("condition `0 <= epsilon[i] < sizes[i]` not fulfilled for all i"); }; 
  for (var G = [1], i = 0; i<sizes.length-1; i++) G[i+1] = G[i] * sizes[i]; 
  for (var n = 0, i = 0; i<sizes.length; i++)  n += G[i] * epsilon[i]; 
  return n;
}

Example :

~ epsilon = greedy_backward(sizes, 29)
1,2,4
~ greedy_forward(sizes, epsilon)
29

Answer 5

Recursion can solve this problem neatly:

function callManyTimes(maxIndices, func) {
    doCallManyTimes(maxIndices, func, [], 0);
}

function doCallManyTimes(maxIndices, func, args, index) {
    if (maxIndices.length == 0) {
        func(args);
    } else {
        var rest = maxIndices.slice(1);
        for (args[index] = 0; args[index] < maxIndices[0]; ++args[index]) {
            doCallManyTimes(rest, func, args, index + 1);
        }
    }
}

Call it like this:

callManyTimes([2,3,5], doSomething);

Answer 6

Instead of thinking in terms of nested for loops, think about recursive function invocations. To do your iteration, you'd make the following decision (pseudo code):

if the list of counters is empty
    then "doSomething()"
else
    for (counter = 0 to first counter limit in the list)
        recurse with the tail of the list

That might look something like this:

function forEachCounter(counters, fn) {
  function impl(counters, curCount) {
    if (counters.length === 0)
      fn(curCount);
    else {
      var limit = counters[0];
      curCount.push(0);
      for (var i = 0; i < limit; ++i) {
        curCount[curCount.length - 1] = i;
        impl(counters.slice(1), curCount);
      }
      curCount.length--;
    }
  }
  impl(counters, []);
}

You'd call the function with an argument that's your list of count limits, and an argument that's your function to execute for each effective count array (the "doSomething" part). The main function above does all the real work in an inner function. In that inner function, the first argument is the counter limit list, which will be "whittled down" as the function is called recursively. The second argument is used to hold the current set of counter values, so that "doSomething" can know that it's on an iteration corresponding to a particular list of actual counts.

Calling the function would look like this:

forEachCounter([4, 2, 5], function(c) { /* something */ });

Answer 7

Set up an array of counters with the same length as the limit array. Use a single loop, and increment the last item in each iteration. When it reaches it's limit you restart it and increment the next item.

function loop(limits) {
  var cnt = new Array(limits.length);
  for (var i = 0; i < cnt.length; i++) cnt[i] = 0;
  var pos;
  do {
    doSomething(cnt);
    pos = cnt.length - 1;
    cnt[pos]++;
    while (pos >= 0 && cnt[pos] >= limits[pos]) {
      cnt[pos] = 0;
      pos--;
      if (pos >= 0) cnt[pos]++;
    }
  } while (pos >= 0);
}

Answer 8

One solution that works without getting complicated programatically would be to take the integers and multiply them all. Since you're only nesting the ifs, and only the innermost one has functionality, this should work:

var product = 0;
for(var i = 0; i < array.length; i++){
    product *= array[i];
}

for(var i = 0; i < product; i++){
    doSomething();
}

Alternatively:

for(var i = 0; i < array.length; i++){
    for(var j = 0; j < array[i]; j++){
        doSomething();
    }
}

Answer 9

There's no difference between doing three loops of 2, 3, 5, and one loop of 30 (2*3*5).

function doLots (howMany, what) {
    var amount = 0;

    // Aggregate amount
    for (var i=0; i<howMany.length;i++) {
        amount *= howMany[i];
    };

    // Execute that many times.    
    while(i--) {
        what();
    };
}

Use:

doLots([2,3,5], doSomething);