Random Numbers without Repeat
Blitz3D Forums/Blitz3D Beginners Area/Random Numbers without Repeat
| ||
| I am trying to find a procedure to print 20 RANDOM numbers (1 thru 20) without repeating any 1 number. I know how to use the RAND command but it still prints some of the same numbers twice. |
| ||
| You could have a go at porting my knuth shuffle code to b3d. |
| ||
Use SeedRnd Millisecs()at the start of your program. |
| ||
make 2 arrays(array_a and array_b) with 20 spaces each, then assign each space in array_a a value that you want to use. Then randomly pick a space in array_a and transfer the number in that space to successive spaces in array_b and move the content in array_a after the one just moved, up one space. Dim num_before(20) Dim num_after(20) num_min=1 num_max=20 test=0 For q = num_min To num_max num_before(q)=q Next For q = num_min To num_max a=Rand(num_min,num_max-test) num_after(q)=num_before(a) For z = a To num_max-1 num_before(z)=num_before(z+1) Next ; num_before(num_max)=0 test=test+1 Next For q= 1 To 20 Print q+" : After: "+num_after(q) Next WaitKey() |
| ||
| Use SeedRnd Millisecs() at the start of your program. What he means, is that he wants to use, say, Rand(1,20) twenty times, and only produce unique results. I did some work with DVDExtra once - a DVD player-based SDK which is severely limited in its use of random numbers (due to the hardware, not the SDK itself). The official work-around for this was to use a system based on prime numbers, as below: SeedRnd MilliSecs() prime = 67 pos = Rand(1,20) For n = 1 To 20 pos = (pos + prime) Mod 20 Print pos Next This example uses 67 as its prime number, but you can use any, and will produce a group of pseudo-randoms between 0-19. The number of randoms required must NOT be a prime number, otherwise it won't work. Not saying you should use this - it generally sucks! But it did the job in otherwise impossible circumstances. Warpy's sample looks just the job. |
| ||
| For small numbers where n<32, Bitwise operation might be more efficient. |
| ||
| Can't you just check if the produced number has already been done and if it has, try for a new one? |
| ||
| Try for a new one will result in longer trial processes at the end of the creation of all numbers. The very last number may take quite some time, even if there is only one possible number left! However, if it isn't a time-critical part then it surely is ok. An other approach would be somethin like this: SeedRnd MilliSecs() Dim n(20) For i=1 To 20 r=Rand(1,21-i) ; instead of creating the random number, we create a random index i2=1 i3=1 While (i3<r) Or (n(i2)<>0) ; But the index is meant only for the not-yet set fields... If n(i2)=0 Then i3=i3+1 i2=i2+1 Wend n(i2)=i Next For i=1 To 20 Print n(i) Next WaitKey() |
| ||
| Shuffling means putting array elements into a random order. The algorithm is trivial:
Assign 1,2,...n to array elements a(1),a(2)...a(n)
For k = n to 2 step -1
Select a random element from a(1)...a(k) and swap it with a(k)
Next
|
| ||
| Overall, there's going to be time spent checking OR time spent re-arranging. I guess it's a toss up which is required. As well as memory use in whether to store an array or such. However, I can' see it being particularly intensive on most PCs, unless the possible number of results is large. |
| ||
| |
| ||
| A small change to my above method, results in large (i.e. x -> n) values are removed from consideration, which may reduce the time taken during the loop in many cases. Still, if the "last number to find" happens to be n or n-1 etc. then it will still take the same time. |
   |