Search code examples
javascriptarraysrandomnumbers

Fill an array with random non-consecutive numbers


I want to create an array (indexes) that should be filled with random numbers from 0 to length - 1.

So if length = 3; then the indexes should extend from 0 to 2, for instance it could be something like: [0, 2, 1].

And there is one condition that we should follow: (God, how can I describe this in English:)

The condition: We don't accept consecutive numbers.

So we shouldn't return :

[0, 1, 2]       => Because 0 and 1 and 2 are consecutive.

[2, 0, 1]       => Because 0 and 1 are consecutive.

[2, 3, 1, 0]    => Because 2 and 3 are consecutive.

Ok, I know there may be an exception, the last element may be consecutive because we have no choice at that point!

I wrote a code but unfortunately, it crashes the browser because of high CPU usage!

Please help, my laptop and I are so much confused!

// generate number from 0 to max (max could include in the result)
function getRandom(max) {
    return Math.floor(Math.random() * (max + 1));
};

// our array to be filled with unordered numbers
let indexes = [];

// we will fill the above array with 0, 1 ,2 ,3 I mean 0 to (length - 1) 
let length = 4;

// loop through indexes so that it is filled with 4 elements
while( indexes.length <= length){

      // get a number randomally from 0 to 3
      let result = getRandom(length - 1);
       // we don't want any repeated number so..
       if(!indexes.includes(result)){     
          // finally here is our condition, we should   
          if( result !== indexes[indexes.length - 1] + 1 ){
              indexes.push(result);
          } else if(indexes.length == length){
            // push the last element to the array despite the condition
            indexes.push(result);
          }
       }

};

console.log(indexes);

Solution

  • Your algorithm takes random values and you have a problem with the last value, if the only left over value is the incremented value of the value before the last value.

    For example, the taken values are 1, 0, 2 and leftover value is 3

              v
    [1, 0, 2, 3]
    

    In this case, there is no other value available, than an unwanted value. This yields to an infinite loop.


    You could take an array of all indices and use a Fisher-Yates shuffle algorithm and shuffle until no consecutive incrementing values are in the array.

    function shuffle(array) { // https://stackoverflow.com/a/2450976/1447675
       var currentIndex = array.length,
           temporaryValue,
           randomIndex;
    
        // While there remain elements to shuffle...
        while (0 !== currentIndex) {
            // Pick a remaining element...
            randomIndex = Math.floor(Math.random() * currentIndex);
            currentIndex -= 1;
    
            // And swap it with the current element.
            temporaryValue = array[currentIndex];
            array[currentIndex] = array[randomIndex];
            array[randomIndex] = temporaryValue;
        }
    
        return array;
    }
    
    let length = 4,
        indices = Array.from({ length }, (_, i) => i);
    
    do indices = shuffle(indices);
    while (indices.some((v, i, a) => v + 1 === a[i + 1]))
    
    console.log(...indices);