Generating a set of unique random numbers

A

Adiabat

Guest
Hi all,

I'd like to know the easiest way to generate a set of random numbers that are guaranteed to all be different. As an example imagine we want to generate all the integers from 1 to 50 and then assign them to a 50 element array.

Thanks!
 

Freddy Jones

Your Main Detective
This question has actually been discussed in great detail and attempted to be solved by many people.

Here's a very good post on your problem
http://stackoverflow.com/questions/...n-integer-array-in-the-c-programming-language

It shouldn't be hard to translate their algorithms to GML.

The easiest way, will not be the most performant, and is more than likely going to be naive algorithm. It looks real clever, but the actual lack of complexity is sometimes problematic.

The most simple would be to loop while your list is smaller than your desired length, and only insert values randomly generated that aren't in the list.
 
C

CaffeineJunky

Guest
The simplest way to do it conceptually is to have an array of 50 numbers, pick a random number between 0 and 49 (the bounds of the array), and then remove the element of the array at the index corresponding to that random number and add it as the next entry of a resulting array. This leaves you with an array of size 49 and array of size 1. Repeating this process again will leave you with an array of size 48 and an array of size 2. Continuing in this fashion, we'll end up with an array of size 50 that is the original array in a random order. Note that this involves you having 50 distinct numbers ahead of time and is a tool for rearranging an existing array into a random order.
 

Freddy Jones

Your Main Detective
Code:
/// My suggestion
var length = argument0 - 1;
var maxRand = argument1;
var list = ds_list_create();
while( ds_list_size(list) != length ){
    var rand = random( maxRand );
    if( !~ds_list_find_index( list, rand ) ){
        ds_list_add( list, rand );
    }
}
return list;
Code:
/// Second suggestion
var list = ds_list_create();
var length = argument0 - 1;
var randIncrease = argument1;
var randIndex = 0;
list[| length] = 0; // removes re-allocation performance reduction
for( var i = 0; i != length; i ++){
    list[| i ] = irandom_range( randIndex, randIncrease );
    randIndex = list[| i];
}
ds_list_shuffle( list );
return list;
edit: separated the algorithms codeblocks to demonstrate both approaches more clearly.
 
Last edited:
A

Adiabat

Guest
Wow! Thanks both for your very prompt replies.

However, I've already started on my second beer of the evening and likely can't do your suggestions full justice. Will get back to you as soon as I sober up.
 

TheouAegis

Member
Wow! Thanks both for your very prompt replies.

However, I've already started on my second beer of the evening and likely can't do your suggestions full justice. Will get back to you as soon as I sober up.
That is right up there with some of my excuses that I have used.

*Clap* *clap* *clap*
 

TheouAegis

Member
///random_set(max,items,min)
var r, n=irandom((argument[0] - 1) div argument[1]);
r[0] = irandom(argument[0]);
for(var i=1; i<argument[1]; i++)
r[ i ] = (r[i-1] + ++n) mod argument[0];​
if argument_count==3
{
base = argument[2]-1;
for(i=0; i<argument[1]; i++)
if r[ i ] < base
r[ i ] = base++;​
}
return r;


Edit: It's still not a "nice" random spread, but at least I fixed the typos.
Edit 2: Removing the second randomization gave it a nicer spread.
 
Last edited:
This would be fore generating random numbers that aren't necessarily part of a sequence. you could use a map first to eliminate any possibility of duplicate numbers. Maps cannot contain more than one key that has the same value. You could continue adding keys to the map until the map has reached a certain size. While you've been adding keys to the map, whenever one is successfully added, you add it to a list or queue so they can be quickly read when needed.
 

Freddy Jones

Your Main Detective
Code:
var list = ds_list_create();
for( var i = 1; i <= 50; i++){
   ds_list_add(list,i);
}
ds_list_shuffle(list);
list is a ds_list with all numbers in random order.
This is basically what Caffeine said to do. It's comparable to my second approach, but it does not create a list of unique "random numbers", it's a list of incremented numbers in a random order.
Mine is almost the same, except it is a list of semi-random numbers. It's not 100% random like my first method because the amount of numbers in a specific range is limited by the scale jumped each time. Mine is more likely to favor the lower divisions of the number range, but like I said in my first post, each algorithm has cons and pros. The simplicity of yours can't be beaten, but in order to get the actual value, and not the order of numbers random, there will be more complexity if he needs that.


///random_set(max,items,min)
var r, n=irandom((argument[0] - 1) div argument[1]);
r[0] = irandom(argument[0]);
for(var i=1; i<6; i++)
r[ i ] = (r[i-1] + irandom(n) + 1) mod argument[0];​

if argument_count==2
for(i=0; i<6; i++)
if r[ i ] < argument[2]
r[ i ] = argument[2];​
return r;
I think you meant to use argument_count == 3, because you're accessing the third argument when using argument[2]. Also, yours is very interesting. Unlike strawbry's where the order is what's random and not the numbers, your numbers are partially randomized but the sequence is semi-predictable. The reason I say this is with yours, when you get to a more limiting range, the wave is much more noticeable. And I think in a situation where it requires random unique numbers, the order is important at this point. Compared to my second algorithm, it's close in approach style, but is replacing the shuffle with an offset to the wave making it more predictable. (Although I love the elegance of your approach).

@TheouAegis I put it into a jsFiddle to test with, tell me if I implemented it wrong. https://jsfiddle.net/Lemony_Andrew/yz0dv30v/


@flyingsaucerinvasion
This would be fore generating random numbers that aren't necessarily part of a sequence. you could use a map first to eliminate any possibility of duplicate numbers. Maps cannot contain more than one key that has the same value. You could continue adding keys to the map until the map has reached a certain size. While you've been adding keys to the map, whenever one is successfully added, you add it to a list or queue so they can be quickly read when needed.
This is essentially my first algorithm, except far, far slower and requires many more steps. The extra-creative way of using maps is very interesting, though. This seems like an approach I wouldn't mind using in JavaScript, but with a few added optimizations.
 

TheouAegis

Member
I knew mine had a bit of a pattern to it. Didn't know if you just wanted a set of random numbers or if you wanted the order randomized too. If the first value is high enough, the set looks partially randomized at least. :rolleyes:

Actually once I added the min part of the code, I ruined it, now that I think about it. If at least two values are less than or equal to the min, then they'll both be the min. Without a min aspect, the code runs fine.
 
Last edited:

Roderick

Member
Code:
var list = ds_list_create();
for( var i = 1; i <= 50; i++){
   ds_list_add(list,i);
}
ds_list_shuffle(list);
list is a ds_list with all numbers in random order.
This is basically what Caffeine said to do. It's comparable to my second approach, but it does not create a list of unique "random numbers", it's a list of incremented numbers in a random order.
Just add one more step:
Code:
while (ds_list_size(list) > numberOfDesiredResults)
{
 ds_list_delete(list, 0);
}
This checks the size of the list and deletes the top item over and over until it has only the appropriate number of results.
 
Last edited:
A

Adiabat

Guest
Sorry for the late reply! Now that sobriety has more less returned just wanted to say thanks to all for your detailed replies and am currently testing the various suggestions.
 
Top