Generate 8 unique random numbers between 1 and 100

Question

Hey guys, i have trouble generating unique random numbers using js. Can someone lend me a hand?

Answer 1

Generate permutation of 100 numbers and then choose serially.

Use Knuth Shuffle(aka the Fisher-Yates shuffle) Algorithm.

JavaScript:

  function fisherYates ( myArray,stop_count ) {
  var i = myArray.length;
  if ( i == 0 ) return false;
  int c = 0;
  while ( --i ) {
     var j = Math.floor( Math.random() * ( i + 1 ) );
     var tempi = myArray[i];
     var tempj = myArray[j];
     myArray[i] = tempj;
     myArray[j] = tempi;

     // Edited thanks to Frerich Raabe
     c++;
     if(c == stop_count)return;

   }
}

CODE COPIED FROM LINK.

EDIT:

Improved code:

function fisherYates(myArray,nb_picks)
{
    for (i = myArray.length-1; i > 1  ; i--)
    {
        var r = Math.floor(Math.random()*i);
        var t = myArray[i];
        myArray[i] = myArray[r];
        myArray[r] = t;
    }

    return myArray.slice(0,nb_picks);
}

Potential problem:

Suppose we have array of 100 numbers {e.g. [1,2,3...100]} and we stop swapping after 8 swaps; then most of the times array will look like {1,2,3,76,5,6,7,8,...numbers here will be shuffled ...10}.

Because every number will be swapped with probability 1/100 so prob. of swapping first 8 numbers is 8/100 whereas prob. of swapping other 92 is 92/100.

But if we run algorithm for full array then we are sure (almost)every entry is swapped.

Otherwise we face a question : which 8 numbers to choose?

Answer 2

1. Populate an array with the numbers 1 through 100.
2. Use this JavaScript code to shuffle it.
3. Take the first 8 elements of the resulting array.

Answer 3

var arr = []
while(arr.length < 8){
  var randomnumber=Math.ceil(Math.random()*100)
  var found=false;
  for(var i=0;i<arr.length;i++){
    if(arr[i]==randomnumber){found=true;break}
  }
  if(!found)arr[arr.length]=randomnumber;
}

Answer 4

Same permutation algorithm as The Machine Charmer, but with a prototyped implementation. Better suited to large number of picks. Uses js 1.7 destructuring assignment if available.

// swaps elements at index i and j in array this
// swapping is easy on js 1.7 (feature detection)
Array.prototype.swap = (function () {
    var i=0, j=1;
    try { [i,j]=[j,i]; }
    catch (e) {}
    if(i) {
        return function(i,j) {
            [this[i],this[j]] = [this[j],this[i]];
            return this;
        }
    } else {
        return function(i,j) {
            var temp = this[i];
            this[i] = this[j];
            this[j] = temp;
            return this;
        }
    }
})();


// shuffles array this
Array.prototype.shuffle = function() {
    for(var i=this.length; i>1; i--) {
        this.swap(i-1, Math.floor(i*Math.random()));
    }
    return this;
}

// returns n unique random numbers between min and max
function pick(n, min, max) {
    var a = [], i = max;
    while(i >= min) a.push(i--);
    return a.shuffle().slice(0,n);
}

pick(8,1,100);

Edit: An other proposition, better suited to small number of picks, based on belugabob's answer. To guarantee uniqueness, we remove the picked numbers from the array.

// removes n random elements from array this
// and returns them
Array.prototype.pick = function(n) {
    if(!n || !this.length) return [];
    var i = Math.floor(this.length*Math.random());
    return this.splice(i,1).concat(this.pick(n-1));
}

// returns n unique random numbers between min and max
function pick(n, min, max) {
    var a = [], i = max;
    while(i >= min) a.push(i--);
    return a.pick(n);
}

pick(8,1,100);

Answer 5

I would do this:

function randomInt(min, max) {
    return Math.round(min + Math.random()*(max-min));
}
var index = {}, numbers = [];
for (var i=0; i<8; ++i) {
    var number;
    do {
        number = randomInt(1, 100);
    } while (index.hasOwnProperty("_"+number));
    index["_"+number] = true;
    numbers.push(number);
}
delete index;

Answer 6

How about using object properties as a hash table? This way your best scenario is to only randomize 8 times. It would only be effective if you want a small part of the range of numbers. It's also much less memory intensive than Fisher-Yates because you don't have to allocate space for an array.

var ht={}, i=rands=8;
while ( i>0 || keys(ht).length<rands) ht[Math.ceil(Math.random()*100)]=i--;
alert(keys(ht));

I then found out that Object.keys(obj) is an ECMAScript 5 feature so the above is pretty much useless on the internets right now. Fear not, because I made it ECMAScript 3 compatible by adding a keys function like this.

if (typeof keys == "undefined") 
{ 
  var keys = function(obj) 
  {
    props=[];
    for (k in ht) if (ht.hasOwnProperty(k)) props.push(k);
    return props;
  }
}

Answer 7

Adam0101's answer is correct. This is a slightly shorter version - the 'found' variable isn't necessary.

I tested this in Firebug.

var arr = [];
while (arr.length < 8){
  var randomnum=Math.ceil(Math.random()*100);
  for(var i=0; i<arr.length; i++){
    if(arr[i]==randomnum){break;}
  }
  arr[arr.length]=randomnum;
}
console.log(arr);

Answer 8

To avoid any long and unreliable shuffles, I'd do the following...

1. Generate an array that contains the number between 1 and 100, in order.
2. Generate a random number between 1 and 100
3. Look up the number at this index in the array and store in your results
4. Remove the elemnt from the array, making it one shorter
5. Repeat from step 2, but use 99 as the upper limit of the random number
6. Repeat from step 2, but use 98 as the upper limit of the random number
7. Repeat from step 2, but use 97 as the upper limit of the random number
8. Repeat from step 2, but use 96 as the upper limit of the random number
9. Repeat from step 2, but use 95 as the upper limit of the random number
10. Repeat from step 2, but use 94 as the upper limit of the random number
11. Repeat from step 2, but use 93 as the upper limit of the random number

Voila - no repeated numbers.

I may post some actual code later, if anybody is interested.

Edit: It's probably the competitive streak in me but, having seen the post by @Alsciende, I couldn't resist posting the code that I promised.

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<html>
<head>
<title>8 unique random number between 1 and 100</title>
<script type="text/javascript" language="Javascript">
    function pick(n, min, max){
        var values = [], i = max;
        while(i >= min) values.push(i--);
        var results = [];
        var maxIndex = max;
        for(i=1; i <= n; i++){
            maxIndex--;
            var index = Math.floor(maxIndex * Math.random());
            results.push(values[index]);
            values[index] = values[maxIndex];
        }
        return results;
    }
    function go(){
        var running = true;
        do{
            if(!confirm(pick(8, 1, 100).sort(function(a,b){return a - b;}))){
                running = false;
            }
        }while(running)
    }
</script>
</head>

<body>
    <h1>8 unique random number between 1 and 100</h1>
    <p><button onclick="go()">Click me</button> to start generating numbers.</p>
    <p>When the numbers appear, click OK to generate another set, or Cancel to stop.</p>
</body>

Answer 9

Shuffling the numbers from 1 to 100 is the right basic strategy, but if you need only 8 shuffled numbers, there's no need to shuffle all 100 numbers.

I don't know Javascript very well, but I believe it's easy to create an array of 100 nulls quickly. Then, for 8 rounds, you swap the n'th element of the array (n starting at 0) with a randomly selected element from n+1 through 99. Of course, any elements not populated yet mean that the element would really have been the original index plus 1, so that's trivial to factor in. When you're done with the 8 rounds, the first 8 elements of your array will have your 8 shuffled numbers.

Answer 10

var arr = [];
while(arr.length < 8){
  var randomnumber=Math.ceil(Math.random()*(100 - arr.length)), i;
  for(i=0; i < arr.length; i++) {
    if(arr[i] <= randomnumber) randomnumber++;
    else break;
  }
  arr.splice(i, 0, randomnumber);
}​

In spite of what you might think, incrementing 'randomnumber' doesn't skew any probabilities - it is mathematically equivalent to removing the previous selections from the array.

It's faster than shuffling an array of 100 values, and does not involve 'repicking'.