Jump to content

Photo

Unique Random Number Generation


17 replies to this topic

#1 LASooner OFFLINE  

LASooner

    Chopper Commander

  • 154 posts

Posted Sat Sep 2, 2017 4:38 AM

I'm trying to generate 6 unique random integers in XB from 0 to 6, I don't want to use the same number twice, what would be the most efficient way of doing that?

 

This is what I came up with and it's dog slow, it basically gets stuck after the 4th number or 5th number.

100 RANDOMIZE
110 CPC(0)=INT(RND*6)
120 PRINT CPC(0);CPC(1);CPC(2);CPC(3);CPC(4);CPC(5)
130 CPC(1)=INT(RND*6)
140 IF CPC(1)=CPC(0) THEN 130
150 PRINT CPC(0);CPC(1);CPC(2);CPC(3);CPC(4);CPC(5)
160 CPC(2)=INT(RND*6)
170 FOR A=0 TO 1
180 IF CPC(2)=CPC(A) THEN 160
190 NEXT A
200 PRINT CPC(0);CPC(1);CPC(2);CPC(3);CPC(4);CPC(5)
210 CPC(3)=INT(RND*6)
220 FOR A=0 TO 2
230 IF CPC(3)=CPC(A) THEN 210
240 NEXT A
250 PRINT CPC(0);CPC(1);CPC(2);CPC(3);CPC(4);CPC(5)
260 CPC(4)=INT(RND*6)
270 FOR A=0 TO 3
280 IF CPC(4)=CPC(A) THEN 260
290 NEXT A
300 PRINT CPC(0);CPC(1);CPC(2);CPC(3);CPC(4);CPC(5)
310 CPC(5)=INT(RND*6)
320 FOR A=0 TO 4
330 IF CPC(4)=CPC(A) THEN 310
340 NEXT A
350 PRINT CPC(0);CPC(1);CPC(2);CPC(3);CPC(4);CPC(5)

I know there's got to be a better way, but my brain has yet to find it. And my programming 'Fu' is weak

 



#2 TheMole ONLINE  

TheMole

    Dragonstomper

  • 760 posts
  • Location:Belgium

Posted Sat Sep 2, 2017 5:44 AM

You could do a Fisher-Yates shuffle. Basically, you initialize an array of six numbers in simple ascending order, and you then shuffle them (like a deck of cards) using the algorithm.

 

The algorithm is simple to implement, and it scales linearly with the size of the array you want to shuffle, so it's a near perfect implementation of what you're looking for.

 

It goes like this (in c-ish pseudo code):

for (counter = length-1; counter > 0; counter--)
{
  rndnumber = rnd(length-1);            // generate random number between 0 and the number of elements left

  tmpnumber = array[counter];           // swap number at the random location to the back of the array
  array[counter] = array[rndnumber];
  array[rndnumber] = tmpnumber;
}

So, without any claims to actual syntactic correctness, I think this is what it would look like in BASIC :) :

100 RANDOMIZE
109 REM INTIALIZE ARRAY
110 FOR i = 0 TO 5
120 CPC(i) = i
130 NEXT i
139 REM START SHUFFLING
140 FOR i = 5 TO 1 STEP -1
150 RNDNUMBER = INT(RND * i)
160 TMPNUMBER = CPC(i)
170 CPC(i) = CPC(RNDNUMBER)
180 CPC(RNDNUMBER) = TMPNUMBER
190 NEXT i
200 PRINT CPC(0);CPC(1);CPC(2);CPC(3);CPC(4);CPC(5)

*edit* Simple explanation of the algorithm: imagine you have six cards. You take a random card from the deck and put it in a discard pile, leaving you with a deck of 5 cards. Simply repeat this until you have no cards left and you will end up with a pile of 6 randomized cards. In the implementation above, the discard pile is simply "the end of the array" and grows downwards, towards the start of the array.

 

You'll notice how this always takes exactly six five loops, you only have to generate one random number per loop and there are no if-then-else statements to be evaluated. This makes for a very fast algorithm.


Edited by TheMole, Sat Sep 2, 2017 6:33 AM.


#3 LASooner OFFLINE  

LASooner

    Chopper Commander

  • Topic Starter
  • 154 posts

Posted Sat Sep 2, 2017 5:24 PM

Cool, I'll try this method. Thanks for the layman explanation as well, just what I need. :-)



#4 RXB OFFLINE  

RXB

    River Patroller

  • 2,803 posts
  • Location:Vancouver, Washington, USA

Posted Sat Sep 2, 2017 5:29 PM

I ran this 6 time and The Mole suggestion only repeated a number 3 times in the same place. But never the same in the rest.



#5 LASooner OFFLINE  

LASooner

    Chopper Commander

  • Topic Starter
  • 154 posts

Posted Sat Sep 2, 2017 5:35 PM

I like to surround myself with smart people just for this reason.



#6 sometimes99er OFFLINE  

sometimes99er

    River Patroller

  • 3,961 posts
  • Location:Denmark

Posted Sun Sep 3, 2017 12:58 AM

You could do a Fisher-Yates shuffle. Basically, you initialize an array of six numbers in simple ascending order, and you then shuffle them (like a deck of cards) using the algorithm.

 

The algorithm is simple to implement, and it scales linearly with the size of the array you want to shuffle, so it's a near perfect implementation of what you're looking for.

 

It goes like this (in c-ish pseudo code):

for (counter = length-1; counter > 0; counter--)
{
  rndnumber = rnd(length-1);            // generate random number between 0 and the number of elements left

  tmpnumber = array[counter];           // swap number at the random location to the back of the array
  array[counter] = array[rndnumber];
  array[rndnumber] = tmpnumber;
}

So, without any claims to actual syntactic correctness, I think this is what it would look like in BASIC :) :

100 RANDOMIZE
109 REM INTIALIZE ARRAY
110 FOR i = 0 TO 5
120 CPC(i) = i
130 NEXT i
139 REM START SHUFFLING
140 FOR i = 5 TO 1 STEP -1
150 RNDNUMBER = INT(RND * i)
160 TMPNUMBER = CPC(i)
170 CPC(i) = CPC(RNDNUMBER)
180 CPC(RNDNUMBER) = TMPNUMBER
190 NEXT i
200 PRINT CPC(0);CPC(1);CPC(2);CPC(3);CPC(4);CPC(5)

*edit* Simple explanation of the algorithm: imagine you have six cards. You take a random card from the deck and put it in a discard pile, leaving you with a deck of 5 cards. Simply repeat this until you have no cards left and you will end up with a pile of 6 randomized cards. In the implementation above, the discard pile is simply "the end of the array" and grows downwards, towards the start of the array.

 

You'll notice how this always takes exactly six five loops, you only have to generate one random number per loop and there are no if-then-else statements to be evaluated. This makes for a very fast algorithm.

 

Weakness. The shuffle never has 0 in the first place, 1 in the second and so on.


Edited by sometimes99er, Sun Sep 3, 2017 2:18 AM.


#7 TheMole ONLINE  

TheMole

    Dragonstomper

  • 760 posts
  • Location:Belgium

Posted Sun Sep 3, 2017 2:57 AM

Weakness. The shuffle never has 0 in the first place, 1 in the second and so on.

 

I don't think that's true. If the sequence of RNDNUMBERs generated happens to be 5, 4, 3, 2, 1 you will end up with 0, 1, 2, 3, 4, 5 as the shuffled result (because you will have swapped each element with itself, effectively leaving them in place).

 

Fisher-yates normally does not add bias and has perfectly even distribution (assuming the random number generator has perfectly even distribution, that is).

 

I have made a mistake in de C pseudo-code above though, that does introduce bias (although it will seem to work). The line that assigns rndnumber should read as follows:

rndnumber = rnd(counter);

(the comment on that line even explicitely says so... ugh :) )



#8 sometimes99er OFFLINE  

sometimes99er

    River Patroller

  • 3,961 posts
  • Location:Denmark

Posted Sun Sep 3, 2017 3:13 AM

Taking your code and adding one line to repeat.

 

Do you see 0 in the first column ? Do you see 1 in the second column ? And so on ... ;)

 

shuffle.gif


Edited by sometimes99er, Sun Sep 3, 2017 3:14 AM.


#9 TheMole ONLINE  

TheMole

    Dragonstomper

  • 760 posts
  • Location:Belgium

Posted Sun Sep 3, 2017 3:25 AM

Well, every iteration of the loop there's only a 1 in 720 chance of that specific combination showing up (6! = 6*5*4*3*2*1 = 720), so it's definitely not surprising that there's no instance of an unmutated array in your screen capture. It's always a bit tricky to demonstrate the correctness of a randomization algorithm by simply running it, so that's why my explanation focused on the algorithm itself, which will in fact allow the unmutated array to show up if the specific sequence of random numbers happens to be generated.



#10 TheMole ONLINE  

TheMole

    Dragonstomper

  • 760 posts
  • Location:Belgium

Posted Sun Sep 3, 2017 3:46 AM

Aaaah, I see what you mean now! You're not talking about the specific sequence 0-1-2-3-4-5, you're talking about the fact that there's never a 0 in the first column, never a 1 in the second, ... Sorry I completely misunderstood!

 

Yes, I misjudged how INT works in TI BASIC. line 150 should be RNDNUMBER = INT(RND * (i + 1))



#11 Willsy OFFLINE  

Willsy

    River Patroller

  • 3,024 posts
  • Location:Uzbekistan (no, really!)

Posted Sun Sep 3, 2017 7:05 AM

6 unique random integers range 0 to 6? So for seven possible integers (0 to 6) you only want 6?

Select a random integer between 0 and 6 and *don't* select that one. Select all the others.

10 S=INT (RND*7)
20 FOR I=0 TO 6 :: IF I=S THEN 30 ELSE PRINT I;
30 NEXT I

Edited by Willsy, Sun Sep 3, 2017 7:09 AM.


#12 senior_falcon OFFLINE  

senior_falcon

    Dragonstomper

  • 946 posts
  • Location:Lansing, NY, USA

Posted Sun Sep 3, 2017 7:41 AM

I think 140 and 150 should be as follows:
 
139 REM START SHUFFLING      (start with deck in order from 0 to 5
140 FOR I=0 TO 5
150 RNDNUMBER=INT(RND*6)     random number from 0 to 5
160 TMPNUMBER=CPC(I)         \
170 CPC(I)=CPC(RNDNUMBER)     swap the two cards
180 CPC(RNDNUMBER)=TMPNUMBER /
190 NEXT I                   go through all 6 cards in deck           
 


#13 TheMole ONLINE  

TheMole

    Dragonstomper

  • 760 posts
  • Location:Belgium

Posted Sun Sep 3, 2017 2:06 PM

6 unique random integers range 0 to 6? So for seven possible integers (0 to 6) you only want 6?

Select a random integer between 0 and 6 and *don't* select that one. Select all the others.

10 S=INT (RND*7)
20 FOR I=0 TO 6 :: IF I=S THEN 30 ELSE PRINT I;
30 NEXT I

 

If the order of the numbers doesn't matter, this works indeed. Clever.



#14 TheMole ONLINE  

TheMole

    Dragonstomper

  • 760 posts
  • Location:Belgium

Posted Sun Sep 3, 2017 2:18 PM

 

I think 140 and 150 should be as follows:
 
139 REM START SHUFFLING      (start with deck in order from 0 to 5
140 FOR I=0 TO 5
150 RNDNUMBER=INT(RND*6)     random number from 0 to 5
160 TMPNUMBER=CPC(I)         \
170 CPC(I)=CPC(RNDNUMBER)     swap the two cards
180 CPC(RNDNUMBER)=TMPNUMBER /
190 NEXT I                   go through all 6 cards in deck           
 

 

 

This will seemingly work, but it introduces bias: because each value is only allowed to show up once, there are 6! (720) permutations possible. But the way you implement it above you have 6^6 (46656) possible ways to achieve a result (each of the six iterations of the loop can generate 6 different values). This way, there will be more than one way to achieve each combination, but since 46656 is not divisible by 720 certain combinations are more likely to occur than others, making the algorithm biased.



#15 senior_falcon OFFLINE  

senior_falcon

    Dragonstomper

  • 946 posts
  • Location:Lansing, NY, USA

Posted Sun Sep 3, 2017 7:05 PM

 

This will seemingly work, but it introduces bias: because each value is only allowed to show up once, there are 6! (720) permutations possible. But the way you implement it above you have 6^6 (46656) possible ways to achieve a result (each of the six iterations of the loop can generate 6 different values). This way, there will be more than one way to achieve each combination, but since 46656 is not divisible by 720 certain combinations are more likely to occur than others, making the algorithm biased.

Well, you and Wikipedia taught me something today about the Fisher-Yates shuffle.  And they say you can't teach an old dog new tricks!



#16 senior_falcon OFFLINE  

senior_falcon

    Dragonstomper

  • 946 posts
  • Location:Lansing, NY, USA

Posted Wed Sep 6, 2017 6:34 AM

I did a little more research into this.  If you have a 3 card deck it is simple enough that you can work it out on a sheet of paper.  Starting with card 1=1, card 2=2 and card 3=3 there are 27 possible outcomes.  Adding up the numbers you get:

 

Card 1: is one 9 times; is two 10 times; is three 8 times

Card 2: is one 9 times;  is two 8 times; is three 10 times

Card 3: is one 9 times;  is two 9 times; is three 9 times

 

I wrote a short program to shuffle a three card deck and add up what cards were in a given position.  I looped 81000 times.  (Compiled and using cpu overdrive as I don't have unlimited patience) and got the following results:

 

          One     Two   Three

Card 1  26923   29829   24248

Card 2  27109   24058   29833

Card 3  26968   27113   26919

 

So it seems the random number generator is pretty good and the only major bias is introduced by my faulty shuffle method.



#17 TheMole ONLINE  

TheMole

    Dragonstomper

  • 760 posts
  • Location:Belgium

Posted Thu Sep 7, 2017 8:44 AM

cool test!



#18 senior_falcon OFFLINE  

senior_falcon

    Dragonstomper

  • 946 posts
  • Location:Lansing, NY, USA

Posted Thu Sep 7, 2017 11:38 AM

I thought about doing it with the proper shuffle routine, but the results above show that the totals would hover around 27000 as they should. 

 

By the way, there is another way to shuffle similar to the right way that gives really, really bad results:

Picture the 3 card deck with card 1=1, card 2=2 and card 3=3. 

Swap card 1 with any of the 3 cards.  Good so far...

Now swap  card 1 with card 1 or card 2.  (The right way is to swap card 2 with card 2 or card 3)

 

There are only 6 possible outcomes, but the bias is terrible:

 

Card one:   is one 2 times; is two 3 times; is three 1 time       

Card two:   is one 2 times; is two 3 times; is three 1 time          

Card three: is one 2 times; is two 0 times; is three 4 times        

 

The moral of the story:  Do it the way the Mole described.


Edited by senior_falcon, Thu Sep 7, 2017 1:35 PM.





0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users