Fill an array with random non-consecutive numbers

Question

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);

Answer 1

I had the same problem simple way to do it, by randomly push or unshift to array list using random signal you can control this signal using conditional statement if signal under 10 push added number Other ways if signal above 10 unshift added number it solved It's me for this problem

const generateRandomUnordered = (min, max) => {
  const numbers = [max, min];
  var temp = min + 1;
  for (i = temp; i < max; i++) {
    var signal = Math.round(Math.random() * (20 - 1) + 1);

    if (signal > 1 && signal < 10) {
      numbers.push(temp);
      temp += 1;
    } else {
      numbers.unshift(temp);
      temp += 1;
    }
  }

  return numbers;
};

console.log(generateRandomUnordered(0, 3));

Answer 2

Its a CPP solution
Here we use concept of Sum of N Terms of AP And Arithmetic Progression.
To change array size just edit

#define ARRAY_SIZE 100

below code have also a testing fiction that check generated array is valid?

void fillArray(array<int,ARRAY_SIZE> &arr,int ssz)  

Problem Statement:- "Fill array using Random function is such a way that number
are unique and no number are consecutive in array.

#include<bits/stdc++.h>
using namespace std;
#define ARRAY_SIZE 100 //this can be change as per your requirment

static int counter=0;
/* Function Validate that final array is valid */
void IsFinalArrayIsValid(array<int ,ARRAY_SIZE> &arr){
    int prev=arr[0];
    for(int i=1;i<ARRAY_SIZE;i++){
        if(prev+1 == arr[i]){
            cout<<"problem final Array:- arr["<<i<<"]="<<arr.at(i);
            return;
        }
        prev=arr[i];
    }
    cout<<"Final generated array is valid\n";
};
static int skipcounter;
void fillArray(array<int,ARRAY_SIZE> &arr,int ssz){
    int sumofAP=((ARRAY_SIZE*(ARRAY_SIZE+1))/2 )-ARRAY_SIZE ;//because it start from 
    int tillApSum=0;
    set<int> uniq_num;
    std::random_device dev;
    std::mt19937 rng(dev());
    std::uniform_int_distribution<std::mt19937::result_type> dist6(0,ARRAY_SIZE-1); // distribution in range [1, 6]
    for(;;){ //its infinite loop because random no may be repeted
        int temp = dist6(rng);
        auto pos=uniq_num.find(temp);
        if (pos == uniq_num.end()){
            if(counter==0){
                uniq_num.insert(temp);
            }else {
                if( (temp-1) == arr[counter-1]){
                    skipcounter++;
                    continue;
                }
                uniq_num.insert(temp);
            }
            arr.at(counter++)=temp;
            tillApSum += temp;
            if(tillApSum==sumofAP){
                break;
            }
        }
    }
}

int main() {
    array<int,ARRAY_SIZE> arr{-1};
    fillArray(arr,ARRAY_SIZE);
    IsFinalArrayIsValid(arr);
    for(int i=0;i<ARRAY_SIZE; i++){ 
        cout<<"arr["<<i<<"]="<<arr.at(i)<<"\t";
        if((i+1)%10==0){
           cout<<endl;
        } 
    }
    cout<<endl;

    cout<<"skip counter="<<skipcounter<<endl;;
}

Its a C program solution

• To Run program in debian based system required install openssl-dev
• For build program:- gcc -Wall -o main main.c hashmap.c -lcrypto
• to run program simply run ./main
• HASH(.c/.h) use directly from internet
• keep all 3 file into same folder
• Note:- this program work array of 0-255 length
• OpenSSL Random number generator

---

#include <stdio.h>
#include <openssl/rand.h>
#include <openssl/crypto.h>
#include "hashmap.h"
#define ARRAY_SIZE 100 //this can be change  0->255

static int counter=0;
struct hashmap *map;

/* Function Validate that final array is valid */
void IsFinalArrayIsValid(int *arr){
    int prev=arr[0];
    for(int i=1;i<ARRAY_SIZE;i++){
        if(prev+1 == arr[i]){
            printf("problem final Array:- arr[%d]=%d\n",i,arr[i]);
            return;
        }
        prev=arr[i];
    }
    printf("Final generated array is valid\n");
};
static int skipcounter;
void fillArray(int *arr,int ssz){
    unsigned char buf[sizeof(int)];
    int sumofAP=((ARRAY_SIZE*(ARRAY_SIZE+1))/2 )-ARRAY_SIZE ;//because it start from 
    int tillApSum=0;
    for(;;){ //its infinite loop because random no may be repete
        if(RAND_bytes(buf,sizeof(buf))!=1){
            continue;
        };
        int temp=((int)buf[0]) % ARRAY_SIZE;
        int *res= hashmap_get(map, &temp);
        
        if(res==NULL){
            if(counter==0){
                hashmap_set(map, &temp);
            }else {
                if( (temp-1) == arr[counter-1]){
                    skipcounter++;
                    continue;
                }
                hashmap_set(map, &temp);
            }
        }
    
        if(res==NULL){
            arr[counter++]=temp;
            tillApSum += temp;
            if(tillApSum==sumofAP){//to ensure all block are filled use Sum of arthmatic progression,and sum is terminating condition
                //printf("\n ###############Condition matched tillApSum=%d\n",tillApSum);
                break;
            }
        }
        OPENSSL_cleanse(buf,sizeof(buf));
    }
    //printf("\n"); 
}
//supporting function of hash map not related to problem
int user_compare(const void *a, const void *b, void *udata) {
    //not needed this fuction but due to 3rd party hash map cause 
    return 0;
}
//supporting function of hash map not related to problem
bool user_iter(const void *item, void *udata) {
    //not needed this fuction but due to 3rd party hash map cause 
    return true;
}
//supporting function of hash map not related to problem
uint64_t user_hash(const void *item, uint64_t seed0, uint64_t seed1) {
    const int *user = item;
    return hashmap_sip(user, sizeof(int), seed0, seed1);
}
//sort function 
int comparator(const void *p, const void *q){
    return *(const int *)p >  *(const int *)q; 
}

int main() {
    int arr[ARRAY_SIZE];
    map = hashmap_new(sizeof(int), 0, 0, 0, user_hash, user_compare, NULL, NULL);
    fillArray(arr,ARRAY_SIZE);
    IsFinalArrayIsValid(arr);
    for(int i=0;i<ARRAY_SIZE; i++){ 
        printf("arr[%d]=%d \t",i,arr[i]);
        if((i+1)%10==0){
           printf("\n");
        } 
    } 
    printf("\nskip counter =%d\n",skipcounter);
    hashmap_free(map);
}

---

Answer 3

You could adapt the modern Fisher-Yates algorithm in the following way:

if a swap of values at indexes i and j would bring a value at index i that is not allowed there because of what was already placed at index i+1, then don't do that swap, but instead do a triplet rotation between those three involved indexes.

Here is the implementation, together with a test of 400 runs:

function shuffled(n) {
    let a = [...Array(n).keys()];
    for (let i = n - 1; i > 0; i--) {
        let j = Math.floor(Math.random() * (i + 1));
        if (a[j]+1 === a[i+1]) { // a swap is going to violate the rule at i/i+1
            // Triple rotation at j, i, i+1 (or, when j == i, swap at i, i+1)
            a[j] = a[i];
            a[i] = a[i+1]--;
        } else { // standard swap
            let temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    // Finally check first two values:
    if (a[0]+1 === a[1]) {
        let temp = a[0];
        a[0] = a[1];
        a[1] = temp;
    }
    return a;
}

// Test this solution:
function verify(a) {
    let set = new Set(a);
    return !a.some((v, i) => v === a[i-1]+1 || !set.has(i));
}

for (let size = 2; size < 6; size++) {
    for (let i = 0; i < 100; i++) {
        let a = shuffled(size);
        if (!verify(a)) throw "not correct";
    }
}
console.log("tests successful");

This has a predictable linear time complexity. No risk of multiple failing attempts.

Answer 4

Updated:

I was comparing the wrong number to check for the non consecutive rule

You can create a list of indexes, take the first item randomly. then remove one item from the indexes at a time if the condition is meet or if it is the last element

const range = (n) => {
    const array = [];
    for (let  i = 0; i < n; i++) array.push(i);
    return array;
};

const randomIndex = (array) => (
    parseInt(array.length * Math.random())
);

const randomNonConsecutive = (n) => {
    const array = range(n);
    const result = array.splice(randomIndex(array), 1);

    while (array.length) {
        const last = result[result.length - 1];
        const next = last + 1;
        const index = randomIndex(array);
        const item = array[index];

        if (item !== next || array.length === 1) {
            result.push(item)
            array.splice(index, 1);
        }
    }

    return result;
}

console.log(randomNonConsecutive(3))
console.log(randomNonConsecutive(4))
console.log(randomNonConsecutive(5))

Answer 5

This maintains a set of possible numbers to choose from, for the next number.

The next number picked from this set is randomly chosen.

If a consecutive number is chosen, then the order is swapped.

No dupes are permitted.

function randomNonConsecutive(upto) {
  const result = []
  let set = Object.keys([...Array(upto)])
  for(let x = 0; x < upto; x++) {
    let index = Math.floor(Math.random()*set.length)
    let insert = set[index]
    if(x > 0 && Number(result[x-1]) === insert-1) {
        [result[x-1], insert] = [insert, result[x-1]]
    }
    result[x] = insert
    set.splice(index,1)
  }
  return result
}

let result = randomNonConsecutive(10)
console.log(result)

Answer 6

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);

Answer 7

With a length of 4, your result array only has a few possible results (see below).

The problem with your function is that if you start with digit(s) that result in no possible answer, it will run forever, and with only 4 possible numbers, the chance of that happening is very high. If 0 or 3 is returned as the first number, it will never find a solution. Same if 1 is returned and the second number is not 3, or if 2 is first and the second number is not 0, etc. updated because comments clarified that descending consecutive numbers are allowed (which seems weird).

You're also going to run forever because your while loop should use indexes.length < length instead of <=

[0, 1, 2, 3] // no
[0, 1, 3, 2] // no
[0, 2, 1, 3] // yes
[0, 2, 3, 1] // no
[0, 3, 1, 2] // no
[0, 3, 2, 1] // yes
[1, 0, 2, 3] // no
[1, 0, 3, 2] // yes
[1, 2, 3, 0] // no
[1, 2, 0, 3] // no
[1, 3, 0, 2] // yes
[1, 3, 2, 0] // yes
[2, 0, 1, 3] // no
[2, 0, 3, 1] // yes
[2, 1, 0, 3] // yes
[2, 1, 3, 0] // yes
[2, 3, 0, 1] // no
[2, 3, 1, 0] // no
[3, 0, 1, 2] // no
[3, 0, 2, 1] // yes
[3, 1, 0, 2] // yes
[3, 1, 2, 0] // no
[3, 2, 0, 1] // no
[3, 2, 1, 0] // yes

What this tells us is that this algorithm is likely to fail because it has no "failure" condition handling when there are no numbers left that can satisfy the conditions. You could have a check for that, and restart if it's the case, but it's still likely to be slow. A different approach would be better.