Random number generator without dupes in Javascript?

Question

I need help with writing some code that will create a random number from an array of 12 numbers and print it 9 times without dupes. This has been tough for me to accomplish. Any ideas?

Zennie

Answer 1

var nums = [1,2,3,4,5,6,7,8,9,10,11,12];
var gen_nums = [];

function in_array(array, el) {
   for(var i = 0 ; i < array.length; i++) 
       if(array[i] == el) return true;
   return false;
}

function get_rand(array) {
    var rand = array[Math.floor(Math.random()*array.length)];
    if(!in_array(gen_nums, rand)) {
       gen_nums.push(rand); 
       return rand;
    }
    return get_rand(array);
}

for(var i = 0; i < 9; i++) {
    console.log(get_rand(nums));
}

Comenius

question: how to repeat this script for 20 time? – Counts

I downvoted because this has an unpredicable run-time, doesn't handle duplicates in the source array gracefully, and in the pathological case, will blow the call stack. This isn't how to solve this problem. – Principate

Answer 2

The most effective and efficient way to do this is to shuffle your numbers then print the first nine of them. Use a good shuffle algorithm.What Thilo suggested will give you poor results. See here.

Edit Here's a brief Knuth Shuffle algorithm example:

void shuffle(vector<int> nums)
{
  for (int i = nums.size()-1; i >= 0; i--)
  {
    // this line is really shorthand, but gets the point across, I hope.
    swap(nums[i],nums[rand()%i]);
  }
}

Blus

Using the proven algorithms you suggest does seem like a better idea if one is serious about it. I'd just like to point out that the algorithm I suggested is not the one discussed unfavourably in "see here". – Tungstate

It isn't the same algorithm, no. But I fear it would still produce the same error if I understand right. There are n^3 outcomes for your algorithm that will land in one of n! boxes. That cannot give an even distribution. Try the experiment in the article with your algorithm and see if it works. – Blus

In the comments to the blog you linked, "my" algorithm is brought up by "fabio". He claims that it works, but with a bigger number of swaps (not just the array size). I'll read up on it a little more, and see if I can prove it right or wrong. Andrew Dunn's proposal below seems statistically correct, too, even though it has performance problems. – Tungstate

I looked at that comment you pointed out. I still feel that the number of paths must be divisible by n! to fit evenly into n! outcomes, but I may be mistaken. I'd be interested to see what you find comparing Knuth's algorithm to yours side by side. And yes, Dunn's algorithm should work (despite performance). – Blus

I am taking it to the statisticians: stats.stackexchange.com/questions/3082/… – Tungstate

Cool. I'll keep my eyes on it. Thanks! Maybe add a link to the Coding Horror article? :) – Blus

Answer 3

If I understand you correctly, you want to shuffle your array.

Loop a couple of times (length of array should do), and in every iteration, get two random array indexes and swap the two elements there. (Update: if you are really serious about this, this may not be the best algorithm).

You can then print the first nine array elements, which will be in random order and not repeat.

Tungstate

Answer 4

This is relatively simple to do, the theory behind it is creating another array which keeps track of which elements of the array you have used.

var tempArray = new Array(12),i,r;
for (i=0;i<9;i++)
    {
    r = Math.floor(Math.random()*12);    // Get a random index
    if (tempArray[r] === undefined)      // If the index hasn't been used yet
        {
        document.write(numberArray[r]);  // Display it
        tempArray[r] = true;             // Flag it as have been used
        }
    else                                 // Otherwise
        {
        i--;                             // Try again
        }
    }

Other methods include shuffling the array, removing used elements from the array, or moving used elements to the end of the array.

Risley

Don't use the above code for professional works though, it is an extremely simple example used to demonstrate the logic behind what you are trying to do (printing 9 values from an array of 12 values in random order). – Risley

It does seem to produce an unbiased sequence of numbers, though. The only problem I can see is performance as it gets increasingly more difficult to find the remaining numbers. – Tungstate

Exactly, while that algorithm will suffice for smaller sets of data, for larger sets, you need to make sure collisions don't occur, either by removing data from the array, or pushing it to the end. – Risley

Answer 5

Try this once:

//Here o is the array;
var testArr = [6, 7, 12, 15, 17, 20, 21];
    shuffle = function(o){ //v1.0
                        for(var j, x, i = o.length; i; j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
                        return o;
                };
shuffle(testArr);

Telegu

Answer 6

Here is a generic way of getting random numbers between min and max without duplicates:

function inArray(arr, el) {
    for(var i = 0 ; i < arr.length; i++) 
            if(arr[i] == el) return true;
    return false;
}

function getRandomIntNoDuplicates(min, max, DuplicateArr) {
    var RandomInt = Math.floor(Math.random() * (max - min + 1)) + min;
    if (DuplicateArr.length > (max-min) ) return false;  // break endless recursion
    if(!inArray(DuplicateArr, RandomInt)) {
       DuplicateArr.push(RandomInt); 
       return RandomInt;
    }
    return getRandomIntNoDuplicates(min, max, DuplicateArr); //recurse
}

call with:

var duplicates  =[];
for (var i = 1; i <= 6 ; i++) { 
    console.log(getRandomIntNoDuplicates(1,10,duplicates));
}

Dauntless

Answer 7

const nums = [1,2,3,4,5,6,7,8,9,10,11,12];
for(var i = 1 ; i < 10; i++){
    result = nums[Math.floor(Math.random()*nums.length)];
    const index = nums.indexOf(result);
    nums.splice(index, 1);
    console.log(i+' - '+result);
}

Cobaltite

The community encourages adding explanations alongisde code, rather than purely code-based answers. As explained here: "While this code may answer the question, providing additional context regarding why and/or how this code answers the question improves its long-term value." – Silverside

Answer 8

var nums = [1,2,3,4,5,6,7,8,9];
var gen_nums = [];

function in_array(array, el) {
   for(var i = 0 ; i < array.length; i++) 
       if(array[i] == el) return true;
   return false;
}

function get_rand(array) {
    var rand = array[Math.floor(Math.random()*array.length)];
    if(!in_array(gen_nums, rand)) {
       gen_nums.push(rand); 
       return rand;
    }
    return get_rand(array);
}

for(var i = 1; i < 9; i++) {
    console.log(get_rand(nums));
}

Radiometer