| View previous topic :: View next topic |
| Author |
Message |
CBailey
Joined: 07 May 2015
Posts: 115
|
 Posted: Fri Mar 17, 2023 11:16 pm Post subject: Random non-repeating numbers |
 |
|
I want to have 8 lights, each one connected to a GPIO pin. I want to be able to light them randomly, but without the same one twice in a row. For example, if they were numbered 1-8, I'd want to do all 8 numbers in a random order, then do all 8 again in a random order. Each group of 8 should use each number only once.
72148536
25176483
63187524
I suppose I could write a routine that picks a number, then rejects it if it was already picked. I didn't know if there was a more elegant way to do this.
(BASCOM-AVR version : 2.0.8.5 ) |
|
| Back to top |
|
 |
CBailey
Joined: 07 May 2015
Posts: 115
|
| Posted: Mon Mar 20, 2023 4:21 am Post subject: |
|
|
Ok, I'll post an answer. I did some research and found the Fisher-Yates shuffle, which does exactly what I need. I don't know if the code I created is random enough, but generally looks OK. If I made a mistake please feel free to point it out. Hopefully this will help someone.
| Code: |
'This code will shuffle a number of numbers to create an output with the same numbers
'but in a different order. This is based on the Fisher-Yates shuffle.
' https://en.wikipedia.org/wiki/Fisher-Yates_shuffle
' 031923 CRB
$regfile = "m328pdef.dat" 'Set the AVR to use.
$crystal = 16000000 'Set the AVR clock.
'
$hwstack = 64 'Set the capacity of the hardware stack.
$swstack = 10 'Set the capacity of the software stack.
$framesize = 40
$SIM
'---------------------------------------------------
Dim ArrayLength as Byte
Dim i as Byte
Dim j as Byte
Dim k as Byte
Dim RandomMax as byte
Dim a (8) as Byte
Dim holdi as Byte
Dim Holdj as byte
StartRandom :
ArrayLength = 8
' We set the initial array numbers:
a (1) = 1
a (2) = 2
a (3) = 3
a (4) = 4
a (5) = 5
a (6) = 6
a (7) = 7
a (8) = 8
For i = ArrayLength to 1 step -1
RandomMax = i + 1
j = RND(RandomMax )
j = j + 1
holdi = a (i )
holdj = a (j )
a (i ) = holdj
a (j ) = holdi
next i
' Now we print the result for testing purposes
for k = 1 to ArrayLength
print a (k ) ;
next k
print
goto StartRandom
|
|
|
| Back to top |
|
|
MWS
Joined: 22 Aug 2009
Posts: 2328
|
| Posted: Mon Mar 20, 2023 3:08 pm Post subject: |
|
|
| CBailey wrote: | | which does exactly what I need. I don't know if the code I created is random enough, but generally looks OK. |
Sure it does?
Distribution of numbers looks odd, especially rows with zero hits.
Number 3 is missing in the first 5 rows, but accumulates in row 7.
I would not expect such obvious pattern, especially at 16,477 samples. |
|
| Back to top |
|
|
CBailey
Joined: 07 May 2015
Posts: 115
|
| Posted: Mon Mar 20, 2023 4:17 pm Post subject: |
|
|
| Well, I THOUGHT it was randon! The first run I did, it didn't quite look right, but the second run seemed much better, so I thought it was just a fluke the first time. However, when I rand it with 4 numbers instead of 8, it looked much less random. |
|
| Back to top |
|
|
MWS
Joined: 22 Aug 2009
Posts: 2328
|
| Posted: Mon Mar 20, 2023 8:57 pm Post subject: |
|
|
While RND() as a pure software function is not truly random, its results seem much better distributed than the samples from your code.
I recall your entry post's requirements as
| Quote: | | have 8 lights, each one connected to a GPIO pin |
which tells you want to blink out the number sequence.
According what I've showed, light number 3 never blinks earlier than the 6th blink, while it massively catches up at the 7th blink.
Watching it would show a pattern, instead of randomness. |
|
| Back to top |
|
|
CBailey
Joined: 07 May 2015
Posts: 115
|
| Posted: Tue Mar 21, 2023 3:13 am Post subject: |
|
|
I've gone over this over and over. Whenever I think I made a good change, the output gets worse. My latest version simply changes this line:
RandomMax = i + 1
to
RandomMax = i
This seems to work, but then the last digit never changes. Could this be a problem with the Fisher-Yates Shuffle? Is there a better one? |
|
| Back to top |
|
|
CBailey
Joined: 07 May 2015
Posts: 115
|
| Posted: Tue Mar 21, 2023 5:33 am Post subject: |
|
|
I believe I fixed it:
| Code: |
'This code will shuffle a number of numbers to create an output with the same numbers
'but in a different order. This is based on the Fisher-Yates shuffle.
' https://en.wikipedia.org/wiki/Fisher-Yates_shuffle
' 032123 CRB
$regfile = "m328pdef.dat" 'Set the AVR to use.
$crystal = 16000000 'Set the AVR clock.
'
$hwstack = 64 'Set the capacity of the hardware stack.
$swstack = 10 'Set the capacity of the software stack.
$framesize = 40
$SIM
'---------------------------------------------------
Dim ArrayLength as Byte
Dim i as Byte
Dim j as Byte
Dim k as Byte
Dim RandomMax as byte
Dim a (8) as Byte
Dim holdi as Byte
Dim Holdj as byte
StartRandom :
ArrayLength = 8
' We set the initial array numbers:
a (1) = 1
a (2) = 2
a (3) = 3
a (4) = 4
a (5) = 5
a (6) = 6
a (7) = 7
a (8) = 8
For i = ArrayLength to 2 step - 1
RandomMax = i - 1
j = RND(RandomMax )
j = j + 1
holdi = a (i )
holdj = a (j )
a (i ) = holdj
a (j ) = holdi
next i
' Now we print the result for testing purposes
for k = 1 to ArrayLength
print a (k ) ;
next k
print
goto StartRandom
|
|
|
| Back to top |
|
|
MWS
Joined: 22 Aug 2009
Posts: 2328
|
| Posted: Tue Mar 21, 2023 11:10 am Post subject: |
|
|
| Looks more evenly distributed, but shows another interesting pattern, number 1 never comes first, 2 never second, a.s.o. |
|
| Back to top |
|
|
CBailey
Joined: 07 May 2015
Posts: 115
|
| Posted: Tue Mar 21, 2023 5:48 pm Post subject: |
|
|
| That's a weird one, thanks! Back to the drawing board... |
|
| Back to top |
|
|
CBailey
Joined: 07 May 2015
Posts: 115
|
| Posted: Wed Mar 22, 2023 1:58 am Post subject: |
|
|
I appreciate your help! I think I've got it this time. I wasn't taking into account that RND(x) would create up to X-1, not x. This code should be better, although it doesn't work right for 4 digits (The last digit is sequential)
| Code: |
'This code will shuffle a number of numbers to create an output with the same numbers
'but in a different order. This is based on the Fisher-Yates shuffle.
' https://en.wikipedia.org/wiki/Fisher-Yates_shuffle
' 032123 CRB
$regfile = "m328pdef.dat" 'Set the AVR to use.
$crystal = 16000000 'Set the AVR clock.
'
$hwstack = 64 'Set the capacity of the hardware stack.
$swstack = 10 'Set the capacity of the software stack.
$framesize = 40
$SIM
'---------------------------------------------------
Dim ArrayLength as Byte
Dim i as Byte
Dim j as Byte
Dim k as Byte
Dim RandomMax as byte
Dim a (8) as Byte
Dim holdi as Byte
Dim Holdj as byte
StartRandom :
ArrayLength = 8
' We set the initial array numbers:
a (1) = 1
a (2) = 2
a (3) = 3
a (4) = 4
a (5) = 5
a (6) = 6
a (7) = 7
a (8) = 8
For i = ArrayLength to 2 step - 1
RandomMax = i
j = RND(RandomMax )
j = j + 1
holdi = a (i )
holdj = a (j )
a (i ) = holdj
a (j ) = holdi
next i
' Now we print the result for testing purposes
for k = 1 to ArrayLength
print a (k ) ;
next k
print
goto StartRandom
|
|
|
| Back to top |
|
|
MWS
Joined: 22 Aug 2009
Posts: 2328
|
| Posted: Wed Mar 22, 2023 5:04 pm Post subject: |
|
|
| CBailey wrote: | | I appreciate your help! |
You're welcome.
| Quote: | | This code should be better, although it doesn't work right for 4 digits (The last digit is sequential) |
Try:
|
|
| Back to top |
|
|
CBailey
Joined: 07 May 2015
Posts: 115
|
| Posted: Wed Mar 22, 2023 5:38 pm Post subject: |
|
|
That seems better, thanks!
Also, I realized my sample was resetting the values after each cycle. I figured randomizing already-randomized values would be better:
| Code: |
ArrayLength = 4
' We set the initial array numbers:
a(1) = 1
a(2) = 2
a(3) = 3
a(4) = 4
a(5) = 5
a(6) = 6
a(7) = 7
a(8) = 8
StartRandom:
|
|
|
| Back to top |
|
|
MWS
Joined: 22 Aug 2009
Posts: 2328
|
| Posted: Wed Mar 22, 2023 8:23 pm Post subject: |
|
|
| CBailey wrote: | | Also, I realized my sample was resetting the values after each cycle. |
Noticed it, should not have any negative effect as long the shuffle works well.
| Quote: | | I figured randomizing already-randomized values would be better: |
Try it out. But think about how big the chance for an array of two is, to be ordered again in the second run 
You know how to log the simulator's terminal window to file? |
|
| Back to top |
|
|
O-Family
Joined: 23 May 2010
Posts: 337
Location: Japan
|
| Posted: Thu Mar 23, 2023 1:04 am Post subject: |
|
|
The RND instruction repeats the same value when the parameter is a power of 2, so it is no longer exactly a random number.
For example, if the parameter is 2,4,8,16,32.
| Code: |
Dim I As Word
Do
I = Rnd(4)
Print I;.
Loop
End
|
The answer is as follows
210321032103210321032103210321032103210321032103210321032103210321032103210321032103210321032103210321032103210321
This matter has been communicated to Mark in the past.
Therefore, if you generate a random number much larger than the required range of numbers and then use only the least significant digits, or if the number exceeds the required range, generate the random number again, etc., you will get a diffuse random number. |
|
| Back to top |
|
|
albertsm
Joined: 09 Apr 2004
Posts: 6173
Location: Holland
|
| Posted: Thu Mar 23, 2023 10:05 am Post subject: |
|
|
just pay attention to the CONFIG RND=32
_________________
Mark |
|
| Back to top |
|
|
|
FAQ
Search
Register
Log in
