Unique Random Number Generation

[LASooner]

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

 

[TheMole]

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 September 2, 2017 by TheMole

[LASooner]

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

[RXB]

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.

[LASooner]

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

[sometimes99er]

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 September 3, 2017 by sometimes99er

[TheMole]

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 )

[sometimes99er]

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 ...

 

Edited September 3, 2017 by sometimes99er

[TheMole]

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.

[TheMole]

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))

[Willsy]

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 September 3, 2017 by Willsy

[senior_falcon]

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

[TheMole]

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.

[TheMole]

 

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.

[senior_falcon]

 

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!

[senior_falcon]

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.

[TheMole]

cool test!

[senior_falcon]

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 September 7, 2017 by senior_falcon