Generate Non-Repeating Random Number From A Set


#1

I am trying to generate a random number from a set of numbers but it does not seem to be working. Basically what I did was I randomly generated a number from a set and kept track of each generated number so that it won't be generated again.

To try to prevent duplicates from being generated, I tried removing each generated number from the set. I even used a while loop to make sure that no previously generated number is selected for redundancy purposes but it still generates duplicates.

Then once the set is empty, it is set again to the old set of numbers so that I can randomly generate a unique number from it again. Please take a look at my code below and help point out why it is generates duplicate numbers:

           var set = [0,1,2,3];
           var previousNum;
           var randNum;
           var arrayElementIndex;

            document.getElementById('Box').onclick = function() {
           // Get a random number from predefined set
            randNum = getRndmFromSet(set); 
            
            // Get another random number if number was the last chosen number in the set 
            while(previousNum == randNum){
              randNum = getRndmFromSet(set); 
            }

            // record the previously chosen number
            previousNum = randNum;    

            arrayElementIndex = set.indexOf(randNum)

            if(set.length > 0){
              set.splice(arrayElindex, 1); 
            }
            else {
              // Reset the set          
              set = [0, 1, 2, 3];          
              randNum = getRndmFromSet(set);
              
              // Get another random number if number was the last chosen number in the set before reset 
              while(previousNum == randNum){
                randNum = getRndmFromSet(set);                                        
              }

              previousNum = randNum;  
              arrayElementIndex = set.indexOf(randNum)
              set.splice(arrayElementIndex, 1);                   
            } 
            }
 
           function getRndmFromSet(set) {
            var rndm = Math.floor(Math.random() * set.length);
            return set[rndm];
           }

#2

I don't see a question here. Other than people looking at your code, what would you like help with? Or what discussion would you like to start with this post?


#3

Hi, thanks for replying. I would like your help in determining why my function generates duplicate numbers.


#4

What I don't understand are the global variables besides set. This seems quite a brittle design.

Despite that I would shorten set already in getRndmFromSet().


#5

The variable previousNum is used to keep track of the old random number that was generated by the previous click of the mouse.

The variable randNum is used to store the new random number that is generated

The variable arrayElementIndex is the index of randNum inside of set.

Hope that helps.


#6

I don't see what that's good for, esp. since the index does not relate to a defined number (since you re-index the array after splicing()).


#7

It is used for removing a number from the set array. Basically every time a unique number is generated it is removed from the set. But to remove it from the set it's index has to be obtained.

Also I reset the set once all numbers have been removed so that I can once again generate a unique number from the set when I click on a button.


#8

Random numbers cannot be random when you remove duplicate values.

Are you after a shuffled bag situation instead?


#9

Hi Paul, thanks for responding. To answer your question, if shuffling gives me a unique number every time I call my generate random number function and if consecutive calls generate unique numbers then yes it is what I am looking for.


#10

Let's see if we can resolve issues with your code as it currently stands.

Using your code as a starting point, I see that you are using arrayElindex in one place instead of arrayElementIndex, which we can easily fix up.

  if (set.length > 0) {
    // set.splice(arrayElindex, 1);
    set.splice(arrayElementIndex, 1);

After doing that though, the code doesn't seem to do much, so let's redo this from the start.

You want to give a set of values to the shufflebag, so that a new random value can be retrieved from that whenever you desire.

The usage for the shufflebag can be as simple as:

var bag = shufflebag.init([0, 1, 2, 3]);
var rand1 = bag.next();
var rand2 = bag.next();

The shufflebag() function starts off with a simple structure built around an IIFE (immediately invoked function expression).

var shufflebag = (function iife() {
  function init(values) {
    ...
  }
  return {
    init: init
  };
}());

When you initialize a bag, that bag then contains a reference to a next function which gives the next number from the bag.

  function next() {
    ...
  }
  function init(values) {
    ...
    return {
      next: next
    };
  }

We'll want two places to store the array. One that contains the initial array that was given, and a separate array for the bag from which we obtain our values.

var shufflebag = (function iife() {
  var initialValues = [];
  var bag = [];
...
  function init(values) {
    initialValues = [...values];
    return {
      next: next
    };
  }

var bag = shufflebag.init([0, 1, 2, 3]);

When we initialize, it doesn't matter if the bag is empty. The next() function will check for an empty bag, and refill it from the initial values if need be, before giving a random value from the bag.

We can use a standard knuthShuffle function to achieve a properly random shuffle of the bag.

  function knuthShuffle(arr) {
    var rand, temp, i;

    for (i = arr.length - 1; i > 0; i -= 1) {
      rand = Math.floor((i + 1) * Math.random()); //get random between zero and i (inclusive)
      temp = arr[rand]; //swap i and the zero-indexed number
      arr[rand] = arr[i];
      arr[i] = temp;
    }
    return arr;
  }
  function next() {
    if (bag.length === 0) {
      bag = [...initialValues];
      bag = knuthShuffle(bag);
    }
    return bag.pop();
  }

Does that work? Let's find out. First we init the bag with values:

<p>
  <label>Random numbers <input name="numbers" value="0, 1, 2, 3"></label>
  <button id="initBag">Init bag</button>
</p>
<button id="showNumber" disabled>Show random bag value</button>
<div id="result"></div>

function initNumberClickHandler() {
  var numbers = document.querySelector("[name=numbers]");
  var showNumber = document.querySelector('#showNumber');
  var values = numbers.value.split(",");
  values = values.map(function (value) {
    return value.trim();
  });
  bag = shufflebag.init(values);
  showNumber.removeAttribute("disabled");  
}

var initNumber = document.querySelector('#initBag');
initNumber.addEventListener("click", initNumberClickHandler);

Then we use a button to show random values from the bag.

function showNumberClickHandler() {
  var result = document.querySelector("#result");
  if (result.innerHTML.length > 0) {
    result.innerHTML += ", ";
  }
  result.innerHTML += bag.next();
}

var showNumber = document.querySelector('#showNumber');
showNumber.addEventListener("click", showNumberClickHandler);

A working demo of the full shuffle bag example is found at https://jsfiddle.net/pmw57/ks2rucfy/


#11

Hi Paul, thanks for taking the time to help. I tested your code in jsfiddle and it appears that duplicate numbers are generated. What I mean is that the same number is generated in consecutive button clicks but I would like each generated number to be different than the one just before it.

The following is what I am seeing when clicking the show random bag value button:
0,3, 2,1, 2,1,3,0,0,2,1,3

In the sequence of numbers above, notice how the number 0 is generated twice one after the other. This is the same problem I was having with my own code. Is there a way to make your code not do that?


#12

The bag contains four numbers. When the bag is emptied it's filled again and shuffled, so with the empty bag being shown, you have:

   0,3,2,1 | 2,1,3,0 | 0,2,1,3

There is a way to deal with that by remembering the previous number that was drawn out.

function showNumberClickHandler() {
  var result = document.querySelector("#result");
  var value = bag.next();
  while (value === bag.lastValue) {
    value = bag.next();
  }
  bag.lastValue = value;

https://jsfiddle.net/pmw57/ks2rucfy/4/

We can now move that lastValue part into the shufflebag code, which lets us push the unwanted value back into the bag for a reshuffle.

  var lastValue;
  ...
  function next() {
    var value;
    if (bag.length === 0) {
      bag = [...initialValues];
      bag = knuthShuffle(bag);
    }
    value = bag.pop();
    while (value === lastValue) {
      bag.push(value);
      bag = knuthShuffle(bag);
      value = bag.pop();
    }
    lastValue = value;
    return value;
  }

And we can then remove the changes that were first made:

    return {
      next: next
      // lastValue
    };
...
  // while (value === bag.lastValue) {
  //   value = bag.next();
  // }
  // bag.lastValue = value;

The updated code with the no-duplicate shuffle bag is at https://jsfiddle.net/pmw57/ks2rucfy/18/


#13

Making this code more usable and configurable, it would certainly be handy to give this code the ability to prevent those duplicates as a configuration option.

  bag = shufflebag.init(values, {
    "preventDuplicates": true
  });

I've made it an option that can be turned on, because the normal default behaviour of a shuffle bag ignores the duplicate issue.

It would also be neat if these configurable options were discoverable on the bag object itself too.

var shufflebag = (function iife() {
  var opts = {
    preventDuplicates: false
  };
  ...
  function init(values, conf) {
    initialValues = [...values];
    opts.preventDuplicates = conf && conf.preventDuplicates;
    return {
      next: next,
      opts: opts
    };
...
console.log(bag);
// next: ƒ next()
// opts:
//   preventDuplicates: true

Now we just need the code to obey that option:

    if (opts.preventDuplicates) {
      while (value === lastValue) {
        ...
      }
      lastValue = value;
    }

We can also add a checkbox on the page to affect the preventDuplicates behaviour:

<p>Live option: <input type="checkbox" name="preventDuplicates" checked> prevent duplicates being shown</p>

function initNumberClickHandler() {
  ...
  var preventDuplicates = document.querySelector("[name=preventDuplicates]");
  ...
  bag = shufflebag.init(values, {
    "preventDuplicates": preventDuplicates.checked
  });
  ...
}

And update the option when it's changed too:

function preventDuplicatesEventHandler(evt) {
  var checkbox = evt.target;
  bag.opts.preventDuplicates = checkbox.checked;
}

var preventDuplicates = document.querySelector("[name=preventDuplicates]");
preventDuplicates.addEventListener("change", preventDuplicatesEventHandler);

The updated code, that defaults to normal shuffle bag behaviour, and can be configured to prevent duplicate values, is at https://jsfiddle.net/pmw57/ks2rucfy/41/


#14

Thank you so much for your help, this is very useful. I will definitely incorporate this into my work.


#15

Hi Paul, I like your solution and I'll definitely make use of it. However, the fact that I was not able to get my own code to work was unsettling so I decided to try to fix it. Fortunately the fix was simple.

Below is my updated code if anyone is interested:

       var set = [0, 1, 2, 3];
       var previousNum;
       var randNum;
       var arrayElementIndex;

       document.getElementById('Box').onclick = function() {
           // Get a random number from predefined set
           randNum = getRndmFromSet(set);

           // Get another random number if number was the last chosen number in the set 
           while (previousNum == randNum) {
               randNum = getRndmFromSet(set);
           }

           // record the previously chosen number
           previousNum = randNum;

           arrayElementIndex = set.indexOf(randNum)

           if (set.length > 0) {
               set.splice(arrayElementIndex, 1);
               if (set.length == 0) {
                   set = [0, 1, 2, 3];
               }
           }

       }

       function getRndmFromSet(set) {
           var rndm = Math.floor(Math.random() * set.length);
           return set[rndm];
       }

closed #16

This topic was automatically closed 91 days after the last reply. New replies are no longer allowed.