Randomizing a list of numbers

Question

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 3-Dec-11 15:40pm

Kevnar

Add a Solution

2 solutions

Solution 1

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

Posted 3-Dec-11 17:59pm

Peter_in_2780

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.

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Kevnar · Accepted Answer · 2011-12-04T08:15:00

Solution 2

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.

Posted 4-Dec-11 8:15am

Kevnar

Updated 4-Dec-11 8:19am

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.