Arbitrary depth nested for-loops without recursion

Question

Suppose I have an array of n values I want to apply nested for-loops over to an arbitrary depth m.

const array = [1, 2, 3];

// 2-depth for-loop
for (const i of array) {
  for (const j of array) {
    // do the thing
  }
}

// 3-depth for-loop
for (const i of array) {
  for (const j of array) {
    for (const k of array) {
      // do the thing
    }
  }
}

The obvious solution is to use recursion. In JavaScript/TypeScript, a generator lends itself well here. For an example problem, let's calculate the probability distribution of the sum of rolling m 6-sided dice.

type Reducer<T, TResult> = (current: T, accumulator?: TResult) => TResult;

function* nestForLoopRecursive<T, TResult>(
  array: T[],
  depth: number,
  reduce: Reducer<T, TResult>
): Generator<TResult> {
  for (const value of array) {
    if (depth === 1) {
      yield reduce(value);
    } else {
      for (const next of nestForLoopRecursive(array, depth - 1, reduce)) {
        yield reduce(value, next);
      }
    }
  }
}

function reduceSum(current: number, prev = 0): number {
  return current + prev;
}

const pips = [1, 2, 3, 4, 5, 6];

interface RollDistribution {
  [key: number]: number;
}

function rollMDice(m: number): RollDistribution {
  const results: RollDistribution = {};

  for (const result of nestForLoopRecursive(pips, m, reduceSum)) {
    results[result] = results[result] !== undefined ? results[result] + 1 : 1;
  }

  return results;
}

for (let m = 1; m <= 3; m++) {
  console.log(`Rolling ${m} ${m === 1 ? 'die' : 'dice'}`);
  console.log(rollMDice(m));
  console.log();
}

Output

Rolling 1 die
{ '1': 1, '2': 1, '3': 1, '4': 1, '5': 1, '6': 1 }

Rolling 2 dice
{
  '2': 1,
  '3': 2,
  '4': 3,
  '5': 4,
  '6': 5,
  '7': 6,
  '8': 5,
  '9': 4,
  '10': 3,
  '11': 2,
  '12': 1
}

Rolling 3 dice
{
  '3': 1,
  '4': 3,
  '5': 6,
  '6': 10,
  '7': 15,
  '8': 21,
  '9': 25,
  '10': 27,
  '11': 27,
  '12': 25,
  '13': 21,
  '14': 15,
  '15': 10,
  '16': 6,
  '17': 3,
  '18': 1
}

My understanding is that any recursive function can be rewritten iteratively, though it usually requires some augmentation. (For example, an in-order traversal of a binary tree can be done iteratively if you augment each node with two bits and a parent pointer.)

How can I rewrite nestForLoopRecursive() without using a stack or any other recursive data structure? In particular, is it possible to do this in at most O(n lg(m)) space?

Here's a CodeSandbox with everything needed written in TypeScript. The code yet to be written starts at line 16. Feel free to answer using whatever language you choose, though, including pseudocode.

Answer 1

It is impossible to do this in $O(n \log m)$ space, by a counting argument. Fix $n = 2$ and consider the number of iterations for which the program must execute. There are $m$ nested loops, each with $2$ indices, so the inner statement executes exactly $2^m$ times and then the iteration terminates. But the configuration space of the program only has $2^{O(\log m)} = \operatorname{poly}(m)$ possible states. So as $m \rightarrow \infty$, by the pigeonhole principle some state must be visited twice during the iteration, which is impossible because it would result in an infinite loop.

On the other hand, you can easily do this in $O(\log(n^m)) = O(m \log n)$ space. (Note that this is reversed from what you wrote!) All you have to do is count in base $n$. That is, keep an array of integers of size $\log n$ and treat them as the base $n$ digits of a single number that you are incrementing. Or you can use an arbitrary precision integer data type and use division and modulo operators to extract the base $n$ digits. Either way, this is trivially equivalent to using a stack, but maybe it feels less "recursive" to you.