random shuffle

[Deucy]

NOTE: this doesn't concern a special language, this is a general algorithm..



imagine a media player.. it has a list of songs to play.. and the user has it on shuffle mode.. so, each time it plays a song, that song shouldn't have been played before.. and so on..

for the sake of simplicity, let's denote the song by a number.. so let's say we have a list of numbers from 1 to 10.. the random generator will pick number 5, and we put that in a list, let's call it playedList.. so the next time the random generator picks up the number 3.. then, it picks number 5 again.. it checks to see if 5 existed before, so it checks playedList.. it was there? pick another number.. and so forth..

so far so good..
but.. this is a list of 10.. imagine at the 9th time, it gets a random number, and it has to check that number with playedList, which by now has 8 numbers.. it doesn't seem like much waste of time.. but what about a list of 100? 1000? a million?

we all know this, which is good.. and widely used..
so i was thinkin' to come up with some kind of a bit-mask checking.. let's say we have a bit-mask variable, call it bitMask.. everytime we generate a number that hasn't been used before, we OR it to bitMask..

here's a simple case scenario:

init
bitMask = 0000

first time
number 4 = 0100
0100 AND 0000 = 0000 != 0100
which means didn't exist before..
set bitMask = bitMask OR 0100 = 0100

second time
8 = 1000
0100 AND 1000 = 0000 != 1000
didn't exist.. execute it..
set bitMask = bitMask OR 1000 = 1100

SIDE-NOTE: now, in bitMask, both 4 and 8 existed before, altho it's represented by one number 1100; 12 in decimal..

third time
2 = 0010
0010 AND 1100 = 0000 != 0010
didn't exist.. execute it..
set bitMask = bitMask OR 0010 = 1110

forth time
4 = 0100
0100 AND 1110 = 0100 != 0100
existed before.. don't execute..
don't change bitMask..

fifth time
1.. simple enough..
bitMask = 1111

SIDE-NOTE: note that so far, bitMask 1111 denotes that the numbers 1, 2, 4, 8 existed before..

sixth time
assume it gets to be the number 15..
15 = 1111..
1111 AND 1111 = 1111 = 1111
this means that 15 existed before, altho we know, for sure, that it didn't..



so, it seemed to be working fine, until the sixth time took place.. do you think we could come up with a workaround?

i appreciate you reading up to THIS POINT..
thank you..

[NotLKH]

There are many ways to do what I believe you're suggesting.
The fastest, easiest way, for me is something like the following:


Dim I_WAS_SELECTED() As Boolean
Dim SelCount As Integer
Dim MyUpper As Integer

Private Sub Command1_Click()
Randomize
Dim SELECTED_1_Thru_MyUpper As Integer '
If SelCount = MyUpper Then
Call REDIM_IT
MsgBox "Starting Over Again!"
End If

SELECTED_1_Thru_MyUpper = Int(Rnd * MyUpper )
While I_WAS_SELECTED(SELECTED_1_Thru_MyUpper ) = True
SELECTED_1_Thru_MyUpper = (SELECTED_1_Thru_MyUpper + 1) Mod MyUpper
Wend
SelCount = SelCount + 1
I_WAS_SELECTED(SELECTED_1_Thru_MyUpper ) = True
SELECTED_1_Thru_MyUpper = SELECTED_1_Thru_MyUpper + 1 '0 thru 14 equiv to 1 thru 15
MsgBox "Number " & SelCount & " Is " & (SELECTED_1_Thru_MyUpper )

End Sub

Private Sub Form_Load()
MyUpper = 15
Call REDIM_IT
End Sub
Private Sub REDIM_IT()
ReDim I_WAS_SELECTED(MyUpper - 1)
SelCount = 0
End Sub


As you can see, an array dimmed as boolean keeps track of whats been chosen. When a random selection is made, if that has been chosen already, the number is incrimented modularly, until an unchosen number is found.

Also, if all the numbers have been chosen, then you reset the arrays and the counter, and start all over again.

However, this is NOT the recommended way to do it, since it still is a time consuming process.

I believe Guv, Jim Macnemara {sp?}, MartinLiss or Plenderj have a good "shuffling" system somewhere around here.

And, I have a way useing copymem to remove elements from an array, without leaving holes, and then reinserting them back in the original order, which is definitely applicable to this problem.

-Lou

[Deucy]

yea, actually this is a good way and similar to what i was lookin' for..

i'm not doin' a project or anything, i'm just concerned (and i always am) about finding an algorithm for this problem that is LEAST time-consuming..

altho i'm not sure what could be less time-consuming, i'd like to know :)

i'll check those guys u just mentioned..

[sql_lall]

The best way i have come up with is this: (pseudo-code)
Start with an array, play_order[1 to MAX_SONGS] = 1,2,3,4
now loop through, swap each one randomly
finish, play play_order[1], play_order[2]...

E.g:


'Assuming you have 10 songs.
'If you have 7, change each '10' to '7' etc...
Dim play_order[10] as integer
Dim a, temp as integer
Dim rand_int as integer
'Put in sub somewhere...
for a = 1 to 10
play_order[a]=a 'initialise
next a
for a = 1 to 10
rand_int=int(rnd*10)+1
temp=play[rand_int]
play[rand_int]=play[a]
play[a]=temp
next a
for a = 1 to 10
'Call you 'play the song' function here
next a


Apologies for any errors, i've been using C++, so am a bit out of touch with VB.
Now, the running time of this is O(n), the same as the hypothesised bit-wise thing. If you have to check if each one before had been used, then this turns into O(n2). I think using the boolean array still results in an O(n2) on average, O(n) for the best case.
BTW, you use something similar tho this when writing something to shuffle cards.

[NotLKH]

This is the code that shuffles 15 numbers useing ShiftMem api.
Basically, it extracts the number you just randomely selected from the stack of remaining possible choices, and reduces the range of choices in an ever decreasing process.


Option Explicit

Dim MyNumbers() As Integer
Dim MyNumberSet() As Integer
Dim MyChosen() As Integer
Dim MyUpper As Integer
Dim MyTop As Integer

Private Declare Sub ShiftMemory Lib "kernel32" Alias "RtlMoveMemory" (hpvDest As Any, hpvSource As Any, ByVal cbCopy As Long)
Private Sub Form_Load()
MyUpper = 15
Call SETUP_SOURCE
Call REDIM_IT
End Sub
Private Sub SETUP_SOURCE()
Dim MyI As Integer
ReDim MyNumberSet(MyUpper - 1)
For MyI = 0 To UBound(MyNumberSet)
MyNumberSet(MyI) = (MyI + 1)
Next MyI
ReDim MyNumbers(MyUpper - 1)
ReDim MyChosen(MyUpper - 1)
End Sub

Private Sub Command1_Click()
Dim SELECTED_1_Thru_MyUpper As Integer '
Dim MyI As Integer
Randomize
Call REDIM_IT
'List1.Clear
MyTop = MyUpper - 1
For MyI = 0 To UBound(MyNumbers)
SELECTED_1_Thru_MyUpper = Int(Rnd * (MyTop + 1))
MyChosen(MyI) = REMOVE_ELEMENTS(MyNumbers, SELECTED_1_Thru_MyUpper, MyTop)
Next MyI
'For MyI = 0 To UBound(MyChosen)
' List1.AddItem MyChosen(MyI)
'Next MyI
End Sub

Private Sub REDIM_IT()
ShiftMemory MyNumbers(0), MyNumberSet(0), 2 * MyUpper
End Sub
Private Function REMOVE_ELEMENTS(ByRef inArr() As Integer, ByRef RemoveWhichOne As Integer, ByRef HowManyToChooseFrom As Integer) As Integer
REMOVE_ELEMENTS = inArr(RemoveWhichOne)
If RemoveWhichOne <> HowManyToChooseFrom Then
ShiftMemory inArr(RemoveWhichOne), inArr(RemoveWhichOne + 1), 2 * (HowManyToChooseFrom - RemoveWhichOne)
End If
HowManyToChooseFrom = HowManyToChooseFrom - 1
End Function


The result is stored in the MyChosen array.


-Lou

[Fragolata]

I would suggest using sql_lall's method of swapping two over again and again, but as a general rule you should do this 5x times, where the amount of numbers in the list is x.

So for a list of 10, swap them 50 times. It's simple, and it works.

[NoteMe]

I havn't read all the post over here, but what about if you have an array of all the songs, and an other array with the songs that have been played. (Use objects, then you only have to change the pointers, because the objects are not in the arrays, just the pointers).

- Every time one is played, place it in the other array.
- Move the songs that is in the play array forward, so you have no holes in the play array (keep track of how many it is in the play array)
- Now pick one of the indexes in the array of the play list, and you will know for sure it has not been played....


for 100 songs this will not take much time. And if you are using objects with pointers in the array, you will not use musch time sorting them out if there is 1000 of them either.....just a tought....

[Deucy]

hold up hold up.. u mixed up two concepts :) u stirred Linked Lists and Arrays together :)..

you said have an array of songs, and each time a song is played, you remove it off the list, and shift up the rest.. now in the worst-case scenario, indeed you were reffered to the song with the index, but might end up shifting the whole list up.. which takes O(n) if they were n songs (right?)..

then you backed up and said if you used pointers, then you won't have much time shifting them up, so you're suggesting Linked Lists (conceptually).. but hold on a second.. back to square one.. you lost the referrence to a song with the index, now you have to traverse through the list to find the song, which again, takes O(n) with n songs :)

this is fine if it's a small list of songs.. but i'm not actually making a media player, i was just discussing the algorithm of randomizing a list (e.g. a Media Player :D)

so far, persaonlly, i find the algorithm in which you fill an array with the numbers ordered and randomly interchange their positions in the list then just traverse through the list iteratively the most-effective easily-implemented algorithm..

[A$$Bandit]

A neat way to shuffle stuff like audio tracks or cards is to stick them in an array and swap random numbers. For example let's say we're using 52 cards. The procedure you'd want to follow would be:

1: Pick 2 random numbers between 1 and 52, call them x and y.
2: Stick card x in a temporary variable.
3: Stick card y where x was.
4: Stick the card from the temporary variable, where y was.
5: Repeat.

For that list of 52 cards I found that 500ms worth of shuffling was plenty. I'm not sure how well this would work for large lists though.

[opus]

You don't have to use that shuffeling thing!
Go for the random pick, but use a second array from which you pick the songs.

PseudoCode:
You have the Songlist (1..10) and the PickList (1..10), the later holds the numbers of Songs from the songlist ( at the beginning that would be easy Picklist(1)=1 Picklist(2)=2 ....) Store the Shuffle in a Playlist(1..10)
First Pick
Pick one INDEX of the PickArray(1..10) and store its Value in Playlist(1). (For example You picked randomly Index 4, Since Picklist(4)=4 You have Playlist(1)=4)
Now remove the picked Index from the Picklist, move all indice which are greater one step down and resize the Picklist.
Note: The Picklist loks like that now Picklist(1)=1, Picklist(2)=2, Picklist(3)=3, Picklist(4)=5,....Picklist(9)=10
Second Pick
Pick one INDEX of the PickArray(1..9) and store its Value in Playlist(2). (For example You picked randomly Index 4, Since Picklist(4)=5 You have Playlist(2)=5)
Now remove the picked Index from the Picklist, move all indice which are greater one step down and resize the Picklist.
Note: The Picklist loks like that now Picklist(1)=1, Picklist(2)=2, Picklist(3)=3, Picklist(4)=6,....Picklist(8)=10
...................
That way you don'T have to draw countless times to find a valid pick. The timeconsuming part would be the rearranging of the picklist after each draw.