Loop from 0 to a number and loop through all numbers in array (javascript)

Question

Here is the idea:

var a = [4, 5, 6];
for (var m = 0; m < a[0]; m++)
  for (var n = 0; n < a[1]; n++)
    for (var p = 0; p < a[2]; p++)
      console.log(`${m} + ${n} + ${p} = ${m+n+p}`);

Live Copy:

// This just tells the Stack Snippets in-snippet console not
// to throw away entries once it reaches a max (the default max
// is just the last 50 logs).
console.config({maxEntries: Infinity});

var a = [4, 5, 6];
for (var m = 0; m < a[0]; m++)
  for (var n = 0; n < a[1]; n++)
    for (var p = 0; p < a[2]; p++)
      console.log(`${m} + ${n} + ${p} = ${m+n+p}`);

/* This just makes the console take up the full output area */
.as-console-wrapper {
  max-height: 100% !important;
}

The code would get longer if the array a has more indexes. Could the code be shorten using Array.map or filter or a function?

Answer 1

It's easier if you break it down. First, you need to create a series per every element of your array.

let series = num => Array.from({ length: num + 1 }, (n, i) => i); //creates an array with nums from  0 to num.

That's the first part of your question. Then you need to do a cross product of your series.

Basically for two series [1, 2, 3] and [1, 2, 3, 4] you'll end up with a set of 12 elements:

[2, 3, 4, 5, 3, 4, 5, 6, 4, 5, 6, 7]

And for that you could do:

let crossProduct = (a1, a2) => Array.prototype.concat.call(...a1.map(n1 => a2.map(n2 => n1 + n2)));

Now all you need to do is have a crossProduct for every series.

let final = numbers.map(series).reduce(crossProduct);

And there you have it:

let numbers = [4, 5, 6];
let series = num => Array.from({ length: num + 1 }, (n, i) => i); 
let crossProduct = (a1, a2) => Array.prototype.concat.call(...a1.map(n1 => a2.map(n2 => n1 + n2)));
let final = numbers.map(series).reduce(crossProduct);
console.log(final);

Edit: If it's from 0 to the number before (e.g. 4 is [0, 1, 2, 3]) then just take the + 1 in the series function.

2nd Edit: Less objects created for your crossProduct:

let crossProduct = (a1, a2) => {
    let resultingSet = [];
    for(let i = 0; i < a1.length; i++)
        for(let j = 0; j < a2.length; j++)
            resultingSet.push(a1[i] + a2[j]);
    return resultingSet;
} //only one array is created

And if you want to avoid having the series on memory all the time:

    let numbers = [4, 5, 6];
    let series = function* (num){
        for(let i = 0; i < num; i++){
            yield i;
        }
    }

    let crossProduct = (set, num) => {
       let resultingSet = [];
       for(let i = 0; i < set.length; i++){
           for(let j of series(num)){
               resultingSet.push(set[i] + j);
           }
       }
       return resultingSet;
    }

    let final = numbers.reduce(crossProduct, [0]);
    console.log(final);

Answer 2

We can do this without taking up massive amounts of memory, and fairly simply, by using recursion:

const process = (array, n, numbers) => {
    if (n < array.length) {
        // Not done yet, recurse once for each number at this level
        const max = array[n];
        for (let i = 0; i < max; ++i) {
            process(array, n + 1, [...numbers, i]);
        }
    } else {
        // Done with this level, process the numbers we got
        console.log(`${numbers.join(" + ")} = ${numbers.reduce((s, e) => s + e)}`);
    }
}

process([4, 5, 6], 0, []);

Live Copy, with cross-checking against your results to ensure the above does the same thing:

// This just tells the Stack Snippets in-snippet console not
// to throw away entries once it reaches a max (the default max
// is just the last 50 logs).
console.config({maxEntries: Infinity});

function thisSolution() {
  const results = [];
  const process = (array, n, numbers) => {
      if (n < array.length) {
          // Not done yet, recurse once for each number at this level
          const max = array[n];
          for (let i = 0; i < max; ++i) {
              process(array, n + 1, [...numbers, i]);
          }
      } else {
          // Done with this level, process the numbers we got
          const result = numbers.reduce((s, e) => s + e);
          results.push(result);
          console.log(`${numbers.join(" + ")} = ${result}`);
      }
  }

  process([4, 5, 6], 0, []);
  return results;
}

function yourSolution() {
    const results = [];
    var a = [4, 5, 6];
    for (var m = 0; m < a[0]; m++)
      for (var n = 0; n < a[1]; n++)
        for (var p = 0; p < a[2]; p++)
          results.push(m + n + p);
    return results;
}

const thisResult = thisSolution();
const yourResult = yourSolution();
if (thisResult.some((entry, index) => entry !== yourResult[index])) {
    console.log("WRONG");
} else {
    console.log("RIGHT");
}

/* This just makes the console take up the full output area */
.as-console-wrapper {
  max-height: 100% !important;
}

This never goes deep into the stack (a.length + 1 stack frames, to be precise, so four in the example case). It builds up a number of temporary arrays (145 in the example case) that max out at a.length entries, releasing them as soon as they aren't needed anymore (a max of four are retained at any given time). Here's the quick and dirty metrics on that:

let maxStack = 0;
let stack = 0;
let totalArrays = 0;
let maxArrays = 0;
let arrays = 0;
// A wrapper for counting stack frames
const process = (...args) => {
    if (++stack > maxStack) {
        maxStack = stack;
    }
    const result = process2(...args);
    --stack;
    return result;
};
const process2 = (array, n, numbers) => {
    if (n < array.length) {
        // Not done yet, recurse once for each number at this level
        const max = array[n];
        for (let i = 0; i < max; ++i) {
            ++totalArrays;
            if (++arrays > maxArrays) {
                maxArrays = arrays;
            }
            process(array, n + 1, [...numbers, i]);
            --arrays;
        }
    } else {
        // Done with this level, process the numbers we got
        //console.log(`${numbers.join(" + ")} = ${numbers.reduce((s, e) => s + e)}`);
    }
}

process([4, 5, 6], 0, []);
++maxArrays;    // To account for the one in the last argument above
++totalArrays;  // "
console.log(`Max stack: ${maxStack}, max arrays: ${maxArrays}, total arrays: ${totalArrays}`);

Answer 3

Another solution that doesn't consume alot of memory and fairly efficient is by using an array that represnt the value of the indexes and update it each iteration. first you create an array that represent in each element the amount of iterations you need to run in order to update the indexes respectively for example for this array [1, 2, 3 ,4 ,5] you will get: [280, 140, 20, 5, 1] this means that index[0] will be updated each 280 iterations, index[1] will be updated each 140 iterations and so on.. totally you will run arr[n] * arr[n-1] * arr[n-2] * .... * arr[0] iterations as you did with ordinary nested for loop.

var arr = [1, 2, 7, 4, 5];

var indexes = Array.from({length: arr.length}, () => 0);
iterationsPerElement = arr.map((_, i) => arr.slice(i+1).reduce((acc, elem) => acc * elem, 1));

var totalIterations = iterationsPerElement[0] * arr[0];

for(var iteration = 1; iteration <= totalIterations; iteration++) {
    // sum those indexes
    console.log(`sum = ${indexes.reduce((acc, index) => acc + index, 0)}`);

    // update indexes
    for(i = 0; i < indexes.length; i++) {
        if(iteration % iterationsPerElement[i] == 0) {
            indexes[i]++;
            // empty the indexes on the right
            for(var j=i+1; j <indexes.length; j++) {
                indexes[j] = 0;
            }
        }
    }
}