# Generate True Random, Non-Repeating Numbers List

I need to create a list of N (200) truly random, non-repeating numbers that range from 1 - N (200 in this case).

I’ve used the built in Random method in Xojo but the results were not that random, especially when my app was relaunched when it would regenerate the random number for the song to play.

I’m now considering new ways to create the list of 200 truly random numbers, without repeats using one of these 3 approaches:

1. Use the ‘Crypto.GenerateRandomBytes’ method and extract numbers from it.
2. On OS X get data from the /dev/random stream.
3. Use an API call to get random numbers from http://www.random.org/clients/http/

I’m intending to build an array of 200 random, non-repeating numbers so that my code can then just move through the array one element at a time and play the song number value of that array element.

Then in another file I will keep track of the last array element number that was played in case the app is relaunched and then the app can continue on from the last song that was played.

I appreciate any help or “you’re doing it wrong, try this instead …” suggestions.

Thanks!

What you actually want is a random permutation of the set [1, 2, …, n]. Loop through once and swap each element with a random element. You can do this with the Random class, just set the seed to Microseconds when you begin… Code from memory.

[code]dim r as Random
dim i, count as integer
dim order() as integer

count = 200

r = new Random
r.seed = Microseconds

for i = 1 to count
order.Append(i)
next

for i = 0 to order.Ubound
x = r.InRange(0, order.Ubound)
z = order(x)
order(x) = order(i)
order(i) = z
next[/code]

If the code works as is, I get a cookie.

I don’t know what the default seed for Random is… but if you use Microseconds, then you will probably not get the same series each launch

``````dim a() as integer
for i as integer = 1 to N
a.append i
next
a.shuffle``````

If you’re going to save the index, you should also save the array. Otherwise, it won’t match what you were playing.

Anyone know how the Shuffle method gets seeded?

Anyone know if the Shuffle method implements the Knuth shuffle algorithm?

It appears to be somewhat similar to what Brad suggested above from my quick review.

Random has a RandomizeSeed method, but you really shouldn’t need it. Can you post the code you’re using now?

Here’s the code - I think part of the issue is that I’m calling ‘mRandomNumber.RandomizeSeed’ each time the method is called and that the random variable is local to the method versus staying around? (I vaguely recall Kem mentioning the scope issue?)

(This old code returns the filename of the song file to play which is the old method versus the new thinking of using an index to another array.)

[code] dim mCurrentDate as new DateMCPClass
dim mRandomSongFileName as string
dim mRandomNumber as new Random
dim mRandomSongIndex as integer
dim mFoundUniqueSong as Boolean
dim mReturnSongFileName as string
dim mMaxSongsInHistoryArray as integer = pMusicFileNames.Ubound / 2

mFoundUniqueSong = false

while ( not mFoundUniqueSong )

``````mRandomNumber.RandomizeSeed

mRandomSongIndex = mRandomNumber.InRange( 0, UBound( pMusicFileNames ) )

if ( pSongIndexesPlayed.IndexOf( mRandomSongIndex ) = -1 ) then // it's not yet in the array of played songs:

LogToFile(CurrentMethodName + ": Found a unique song index = " + str( mRandomSongIndex ) )

// The song wasn't found in the last played songs list. Add it:

pSongIndexesPlayed.Append mRandomSongIndex

if ( pSongIndexesPlayed.Ubound > mMaxSongsInHistoryArray ) then

LogToFile(CurrentMethodName + ": pSongIndexesPlayed is greater than " + str( mMaxSongsInHistoryArray ) + " songs, removing the oldest one from the list = " + str( pSongIndexesPlayed(0) ) )

pSongIndexesPlayed.Remove(0) // Remove the oldest array element from the list

end if

mFoundUniqueSong = true

else

LogToFile(CurrentMethodName + ": The random song index selected (" + str( mRandomSongIndex ) + ") was already found in the songs index list. Obtaining a new random song index." )

end if
``````

wend

mReturnSongFileName = pMusicFileNames( mRandomSongIndex )

LogToFile(CurrentMethodName + ": Returning song titled: " + mReturnSongFileName)

return mReturnSongFileName

[/code]

I see what you’re doing. You pick a random song and compare it to the “already played” list. If it’s there, you pick a new song. If it’s not, you add it to “already played”, and that list is only allowed to be half the size of the song list. All songs are not guaranteed to be played, but no song can be played again until half the remaining songs have been played.

I’d remove RandomizeSeed as it’s really not needed here. Every Random object started at a new seed anyway. I’d also use Static instead of Dim for your Random object so you keep working off the same seed.

In terms of performance, you might consider two arrays, an available list and an already played list. You can use the same scheme, but just move tracks between the lists. That way you can lose the entire loop and probably achieve a better distribution.

``````    mRandomSongIndex = mRandomNumber.InRange( 0, UBound( pSongIndexesAvailable ) )
LogToFile(CurrentMethodName + ": Found a unique song index = " + str( pSongIndexesAvailable( mRandomSongIndex ) ) )
pSongIndexesPlayed.Append pSongIndexesAvailable( mRandomSongIndex )
mReturnSongFileName = pSongMusicFileNames( pSongIndexesAvailable( mRandomSongIndex ) )
pSongIndexesAvailable.Remove mRandomSongIndex

if pSongIndexesPlayed.Ubound > pSongIndexesAvailable.Ubound then
LogToFile(CurrentMethodName + ": pSongIndexesPlayed is greater than " + str( mMaxSongsInHistoryArray ) + " songs, removing the oldest one from the list = " + str( pSongIndexesPlayed(0) ) )
pSongIndexesAvailable.Append pSongIndexesPlayed( 0 )
pSongIndexesPlayed.Remove 0
end if``````

Nothing here was tested so forgive typos.

I just tried my scheme and got a lousy distribution. And then I inserted Shuffle and got a much better one each time I tried it.

``````    if pSongIndexesPlayed.Ubound > pSongIndexesAvailable.Ubound then
LogToFile(CurrentMethodName + ": pSongIndexesPlayed is greater than " + str( mMaxSongsInHistoryArray ) + " songs, removing the oldest one from the list = " + str( pSongIndexesPlayed(0) ) )
pSongIndexesAvailable.Append pSongIndexesPlayed( 0 )
pSongIndexesPlayed.Remove 0
pSongIndexesAvailable.Shuffle
end if``````

My test is with 50 indexes played 200 times. Here are distributions per index in three runs.

``````0: 1
1: 2
2: 5
3: 3
4: 6
5: 4
6: 4
7: 1
8: 4
9: 8
10: 3
11: 3
12: 3
13: 7
14: 4
15: 8
16: 3
17: 3
18: 4
19: 3
20: 7
21: 5
22: 4
23: 13
24: 3
25: 2
26: 3
27: 6
29: 5
30: 4
31: 4
32: 2
33: 1
34: 4
35: 2
36: 4
37: 1
38: 6
39: 4
40: 5
41: 4
42: 5
43: 7
44: 7
45: 2
46: 5
47: 2
48: 3
49: 1
0: 2
1: 2
2: 6
3: 5
4: 6
5: 5
6: 6
7: 2
8: 9
9: 5
10: 2
11: 4
12: 4
13: 4
14: 3
15: 7
16: 4
17: 6
18: 7
19: 5
20: 5
21: 4
22: 4
23: 7
24: 4
25: 3
26: 1
27: 10
28: 3
29: 3
30: 4
31: 2
32: 1
33: 1
34: 3
35: 2
36: 6
37: 4
38: 3
39: 1
40: 3
41: 1
42: 5
43: 9
44: 3
45: 2
46: 5
48: 4
49: 3
0: 1
1: 3
2: 7
3: 2
4: 6
5: 5
6: 4
8: 5
9: 5
10: 3
11: 5
12: 2
13: 6
14: 4
15: 9
16: 5
17: 4
18: 6
19: 3
20: 3
21: 5
22: 5
23: 6
24: 2
25: 3
26: 4
27: 5
29: 10
30: 4
31: 3
32: 4
33: 3
34: 3
36: 8
37: 1
38: 7
39: 2
40: 5
41: 3
42: 1
43: 11
44: 4
45: 2
46: 4
48: 4
49: 3``````

Having tried all this, I still think it’s better if you just shuffle the indexes initially and loop the playlist.

Shuffle once, then walk through the array sequentially. Don’t over complicate this. You will have to save the list plus the current index if you want to pick up where you left off.