I was going to reply but didn't have much to say so decided to let others chip in instead. But I guess nobody else sees that this is a great solution. Very simple. Even elegant. (And I proposed it a long time ago when this question came up. :)
If you don't want to hear the same song "too soon" after it was last played (where "soon" is measured in how many songs you've listened to; I don't want more repeats just because I've been listening less frequently of late), then you simply designate how many songs must play between repeats. 1/2 of the collection is a great value for this parameter.
Then you just pick between the rest of the list at random (and push to the end of the list just like you described). You can get fancy and weight the selection toward the front of the list (the songs that haven't been played in the longest time), but by picking "1/2 of the collection" as the dividing point, there just isn't much gain to be had especially considering the added complexity over a simple rand(@songs/2).
My only improvement would be to mention splice.
If I were implementing this in firmware, then I'd probably have two "circle buffers" for holding the two halves of the song list. You'd start with a standard shuffle of the songs into a single list. Then mark the middle of that list as the boundary between your two buffers. Then pick a song at random from the first buffer. You swap that song with the song at the 'head' of the second circular buffer. Then you advance the head of that buffer so that the currently playing song is now at the tail of that buffer.
By avoiding getting fancy (avoiding weighting the random selection from the first buffer), we don't have to keep the first circular buffer sorted so all of our operations are extremely efficient in both space and time.
This algorithm can also be useful outside of firmware constraints given that you probably want to have your randomized playlist be persistent so that the next day your don't start hearing repeats from yesterday. And doing the equivalent of splice on a flat file or even SQL database can be a pain (and slow).
So insert all of you songs into a simple DB, assigning them play-order numbers from 1..N. Keep track of how many songs you have, $N. Keep track of the last song played, $L (initially 1). When you want to play a song, pick song $P= int( $N - rand($N)/2 ). Increment $L but set it to 1 if it goes beyond $N/2. Execute "update songs set playorder = ? - playorder where playorder in (?,?)" for $L+$P,$L,$P. That is all you need for the perfect persistent shuffle.
When you add a new song to your collection, just add it into the table with playorder $N+1 (the new value for $N for the next time you play a song). When you delete a song with playorder $D (do people ever delete songs rather than just getting more storage?), delete it from your database then "update songs set playorder = ? where playorder = ?" for $D,$N. Decrement $N after that, of course.
- tye
In reply to Re: Music shuffling (elegant)
by tye
in thread Music shuffling
by oko1
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |