Click here to Skip to main content
15,944,835 members
Please Sign up or sign in to vote.
4.00/5 (1 vote)
See more:
I need to randomize a list of numbers (song indexes) so that each number is shuffled into a random order and appears only once. It's part of the shuffle function of a song playlist that's currently 13,700 songs. Here's what I have so far:

VB
Dim i As Integer
Dim j As Integer
Dim t As Integer
Dim x As Integer
Dim f As Boolean
Dim s As Date
Dim e As Long

Randomize Timer
t = UBound(URLPathList)
s = Now
Do
    ReDim Preserve PlayList(i)
    f = False
    Do
        x = Int(Rnd * t + 1)
        For j = 0 To i
            If PlayList(j) = x Then f = True
        Next j
        DoEvents
    Loop Until f = False
    PlayList(i) = x
    i = i + 1
Loop Until i = t

e = DateDiff("s", s, Now)
MsgBox e & " seconds"


Unfortunately, the loops and counterloops take way too long to process as the size of the URLPathList is about 13,700 songs. It's probably the worst possible way I could have done this. But it was the first idea in my head.

What I need is a fast, efficient way to randomize a list of numbers between 0 and t, so that each number shows up at least once and only once. I'm gonna keep trying a few things, but if someone comes up with an alternate idea that gets the count of e as small as possible, you win a free virtual cookie.

Thanks in advance.
Posted

What you need is a "shuffle". Try this (written in pseudocode)

initialise an array with the numbers, so arr[i] = i for i = 0 to (13700 or whatever)
repeat until bored (100,000 is probably more than enough)
    let q be a random number between 0 and (13700 or whatever)
    swap arr[0] and arr[q]

Now you have the array you want. This is a very simple but effective technique, and it won't take forever to run.

Peter
 
Share this answer
 
Comments
Kevnar 4-Dec-11 14:14pm    
Thanks for your help. I found a pretty elegant solution. Instead of chosing random numers and putting it sequentially into the array and then checking if it's already been there, I did it the other way around. Go through each number sequentially and put it in a random place in the array. It's much easier to check if one array index is empty than to search through an entire array 13,700^13,700 times. It did all 13,700 numbers in less than a second this way.
VB
Dim i As Integer
Dim t As Integer
Dim X As Integer
Dim s As Date
Dim e As Integer

Randomize Timer
t = UBound(URLPathList)
s = Now

For i = 0 To t
    ReDim Preserve PlayList(i)
    PlayList(i) = -1
Next i

For i = 0 To t
    Do
        X = Int(Rnd * (t + 1))
    Loop Until PlayList(X) = -1
    PlayList(X) = i
Next i

e = DateDiff("s", s, Now)
'MsgBox e & " seconds"


There still may be a better way to do this. I'm open to other methods if you have any. Let me know.
 
Share this answer
 
v3
Comments
Peter_in_2780 4-Dec-11 18:10pm    
Your method is still O(N^2). Consider placing the last number. You have to "wait" for the random number generator to land on the one vacant spot in your array (and the one before it, there are only two spots to hit, and so on). The shuffle method I showed is O(N) - make the loop count say 5 times your array size. For 13000, it doesn't really matter, but for a few million there is a big difference. Try it.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900