4

We have a numerical array with arbitrary max values for each element. How do we increment the elements so the array would go from [0, 0, 0] to [x, y, z]?

To illustrate if the max array is [2, 1, 2] and we start the main array at [0, 0, 0] incrementing should take the main array through these steps:

[0, 0, 0]
[1, 0, 0]
[2, 0, 0]
[0, 1, 0]
[1, 1, 0]
[2, 1, 0]
[0, 0, 1]
[1, 0, 1]
[2, 0, 1]
[0, 1, 1]
[1, 1, 1]
[2, 1, 1]
[0, 0, 2]
[1, 0, 2]
[2, 0, 2]
[0, 1, 2]
[1, 1, 2]
[2, 1, 2]

I have written a function which stops incrementing as soon as it reaches a max of 1. Here is my code:

var maxes = [2, 1, 2];
var myArray = [0, 0, 0];

function step() {
  for(var i = 0; i < myArray.length; i++) {
    if(myArray[i] == maxes[i]) {
       continue;
    } else {
       myArray[i] = myArray[i] + 1;
       return;
    }
  }
  return false;
}

for(j = 0; j < 100; j++) {
  result = step();
  if(!result) break;
  console.log(result);
}
Majid Fouladpour
  • 29,356
  • 21
  • 76
  • 127
user1920050
  • 41
  • 1
  • 2
  • 2
    it is hard to follow the pattern you are looking for, are you trying to calculate with base(4) ? You should at least provide a mathematical formulas to follow. – Mehdi Karamosly Dec 20 '12 at 21:55
  • @MehdiKaramosly, the *formula* is simple, increment the leftmost element that is still below the max for that element. If all elements are at their maxes, return false. – user1920050 Dec 20 '12 at 22:00
  • You can use a simplified version of my answer in http://stackoverflow.com/questions/13742093/create-array-with-all-unique-combinations/13742505#13742505 – Barmar Dec 20 '12 at 22:01
  • @Shredder, actually this could be thought of as a base `n` number with two exceptions (i) each digit has it's own base which is the max, and (ii) we are writing the number right to left. – user1920050 Dec 20 '12 at 22:07
  • Don't forget to upvote any answers that helped you and accept an answer if it solved it. – redolent Jan 14 '13 at 23:19

5 Answers5

1

Fair disclosure: This is my own question. I did not have access to my SO or email logins and posted this question with a new account just then created for a friend. I am not upvoting the question or him the answer. Neither would I have my friend mark my answer as accepted. Anyway, I worked on the problem and eventually came by this working code:

var maxes = [4,1,2,3];
var pattern = [0,0,0,0];

function step() {
  var t = false;
  for(var k = 0; k < pattern.length; k++) {
    t = t || (pattern[k] < maxes[k]);
  }
  if(!t) return false;
  for(k = 0; k < pattern.length; k++) {
    if(pattern[k] < maxes[k]) {
      pattern[k]++;
      return true;
    } else {
      pattern[k] = 0;
      continue;
    }
    return false;
  }
}

console.log(pattern);
var r = true;
while(r) {
  r = step();
  console.log(pattern);
}

JSBin here.

Majid Fouladpour
  • 29,356
  • 21
  • 76
  • 127
0

You need two loops - one for each maxes element, 4 of them currently, but I'm not sure if you plan to change it to be dynamic; and the other loop that will increment values of each element until it reaches its limit value from maxes.

Shomz
  • 37,421
  • 4
  • 57
  • 85
0

You just have some bugs to work out:

var maxes   = [3, 1, 2, 1];
var myArray = [0, 0, 0, 0];

function step() {
  var changed = false;
  for(var i = 0; i < myArray.length; i++) {
    if(myArray[i] == maxes[i]) {
       continue;
    } else {
       myArray[i] = myArray[i] + 1;
       changed = true;
    }
  }
  return changed;
}

for(j = 0; j < 100; j++) {
  result = step();
  if(!result) break;
  console.log(myArray.join(", "));
}
redolent
  • 4,159
  • 5
  • 37
  • 47
0

I revisited this problem a few days ago, and refactored the code a bit.

First to understand the problem properly, it is equivalent to counting in a hybrid-base number system. In this system we have an arbitrary base per position/digit. If all the maxes are 2 for instance the problem then would be counting in base-2, but the maximum for each position could be a different number, hence, the hybrid base system.

The central function is actually very simple:

// increment in hyper system
function incr(maxes,num,digit) {
  num[digit] = num[digit] + 1;
  num[digit] = num[digit] % (maxes[digit]+1);
  if(num[digit] === 0) incr(maxes,num,digit+1);
}

And here's a working jsbin.

Majid Fouladpour
  • 29,356
  • 21
  • 76
  • 127
-1

Here's a simpler, more efficient solution: Simply take a variable pos that stores the current position in the array. Once we've reached max at the current position, we increment the current position by 1, otherwise increment the value at the current position. And that process you just keep repeating until pos has reached the last value and the last value is at max.

var maxes = [3, 1, 2, 1];
var myArray = [0, 0, 0, 0];
var pos = 0;

while (pos < myArray.length - 1 || myArray[pos] < maxes[pos]) {
    if (myArray[pos] >= maxes[pos]) {
        myArray[pos] = 0; // to set it back to zero
        pos++;
        continue;
    } 
    myArray[pos]++;

    // Step code here
}

Works with any sized array. Here's a jsfiddle

Tyron
  • 1,938
  • 11
  • 30
  • Thank you, but the output is not correct. From `3,0,0,0` we should go to `0,1,0,0` not `3,1,0,0` – user1920050 Dec 20 '12 at 22:15
  • the result doesn't look like the example he gave / – Mehdi Karamosly Dec 20 '12 at 22:15
  • Ow k. Then we'll just add the line "myArray[pos] = 0;" to reset the value again. – Tyron Dec 20 '12 at 22:18
  • I would only miss a return if it were a javascript function, but it's not. According to the original question it should only stop at max, not return anything. I clarified now where the step code should go. – Tyron Dec 20 '12 at 22:21
  • yes and the max should be in the above case : [3,1,2,1] and with the edit I have made to your code(in order to set to zero when it reaches the max) it gives : [0,0,0,1] – Mehdi Karamosly Dec 20 '12 at 22:29
  • Incorrect answer. This code (using your JSFiddle example) doesn't produce the desired output. It only increments each individual index value from 0 to its own max, without accounting for the subvariants, like [1,1,0,0]. – Chris Perry Apr 09 '21 at 00:30