Surprisingly, (that is, against my own intuition) it does seem remarkably fair.

If you do just N * 2 cycles (-I=100) it occasionally only picks 48 or 49 of the 50 possibles, but other times it will have picked all 50, which seems well within the bounds of probability. And if you run it for 1e6 cycles, the distribution seems very even. Given the lousy performance of the default rand on my system, it again all seems to be well within statistical boundaries:

#! perl -slw
use strict;

my @tracks = 1 .. 50;

my %picks;

our $I ||= 1e5;

for ( 1 .. $I ) {
    push @tracks, splice @tracks, rand( @tracks/2 ), 1;
    printf "$tracks[ -1 ] " unless $picks{ $tracks[ -1 ] };
    $picks{ $tracks[ -1 ] }++;
}
print "\nPercentage picked: ", keys( %picks ) / @tracks * 100;
printf "track %2d picked %5d times\n", $_, $picks{ $_ }
    for sort{ $picks{ $b } <=> $picks{ $a } } keys %picks;

__END__
c:\test>junk6 -I=1e6
1 14 18 23 7 5 28 26 3 16 33 36 8 17 30 4 40 24 2 39 34 9 35 11 46 25 
47 15 49 37 50 19 41 6 38 21 10 20 44 13 43 12 27 42 45 29 22 31 48 32
Percentage picked: 100
track 14 picked 20145 times
track 35 picked 20124 times
track 25 picked 20117 times
track 12 picked 20109 times
track 40 picked 20104 times
track 10 picked 20102 times
track 30 picked 20087 times
track  4 picked 20086 times
track 11 picked 20075 times
track 16 picked 20073 times
track 47 picked 20068 times
track 18 picked 20065 times
track  2 picked 20050 times
track  7 picked 20045 times
track 26 picked 20041 times
track 24 picked 20038 times
track 39 picked 20038 times
track 45 picked 20038 times
track 20 picked 20031 times
track 48 picked 20031 times
track  8 picked 20029 times
track 38 picked 20027 times
track  5 picked 20021 times
track  6 picked 20015 times
track 15 picked 20014 times
track 28 picked 20002 times
track 13 picked 19985 times
track 34 picked 19981 times
track 50 picked 19980 times
track  9 picked 19977 times
track 17 picked 19976 times
track 37 picked 19975 times
track 32 picked 19966 times
track 23 picked 19964 times
track 21 picked 19961 times
track  1 picked 19957 times
track 41 picked 19953 times
track 36 picked 19947 times
track 42 picked 19946 times
track 44 picked 19936 times
track  3 picked 19934 times
track 43 picked 19931 times
track 49 picked 19921 times
track 29 picked 19914 times
track 27 picked 19901 times
track 31 picked 19889 times
track 19 picked 19887 times
track 22 picked 19879 times
track 46 picked 19874 times
track 33 picked 19791 times
[download]

That said. Shuffling once and then just picking from the front would seem to be easier.

What a great analysis - thank you and ++! My problem here, I suppose, is that I'm not much of a mathematician (hangs head in shame) - I know how to do a frequency count - I just didn't think of doing one to analyze this thing for fairness.

That said. Shuffling once and then just picking from the front would seem to be easier.

Wouldn't that still leave a possible collision problem at the point where the two lists join? Or did I misunderstand what you're describing?

-- 
Human history becomes more and more a race between education and catastrophe. -- HG Wells

Wouldn't that still leave a possible collision problem at the point where the two lists join?

Which two lists? ;)

Assuming a single list of tracks:

use List::Util qw[ shuffle ];

my @tracks = shuffle readTracks( 'myMusicDB' );

while( $listening ) {
    push @tracks, ( my $nextTrack = shift @tracks );
    play $nextTrack;
}
[download]

By shuffling all your tracks once, when you load them, and then picking from the front (shifting) and replacing at the back (pushing), you are guarenteed to never hear the same track again until you've heard every other track. And you'll never know what track is coming next in any given cycle.

If your list is short and you resent being able to predict what you will hear next when the loop repeats, you could always remember the first track (post shuffle) and re-shuffle when it comes around again.

Of course that leaves you open to the possibility of hearing the same track twice in succession when you re-shuffle. Which I guess is what you mean by "two lists".

My math is pretty much limited to "arithmetic", also. That is, without I go look up the particular more advanced stuff I need for any particular thing. A side-effect of of a career of general programming as opposed to consitantly working in a particular field. A bit like a GP versus a consultant. You may cover much of the ground briefly during training, but you either use it, or loose it!

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

One variation of your method might be to use something like(rand()**3)*($N*.95). This makes it possible but highly unlikely for a song just played to play again quite soon. rand()**3 strongly favors songs at the beginning of the list

Personally I use a jukebox program where I put the songs in directories that were given different weights. If there were directories a, b and c, the files in b would be played 2 times as often as the songs in dir c, and the songs in a 3 times as often. The ordering is simply alphabetical

you could as well play them strictly round robin and wouldn't notice any difference.

Well, yes - but even with my (fairly large) collection, I'd still have a problem with hearing a pattern after a while. This approach can run forever without that. I suppose that I could also play the entire list, shuffle it, and then play it again, with a small possibility of a repeat at the "join" - maybe even reshuffle if any of the X last-played songs are found in the first X entries of the new list - but I didn't think of that approach until just now. :)

-- 
Human history becomes more and more a race between education and catastrophe. -- HG Wells

well ..., if you want to add some code back in and your don't play criterion is "I heard it recently", then you could tag pushed back songs with a "last played" time and then base the portion of the array that you may chose from on the set of songs that haven't been played recently.

That's close to what I did originally: a hash with the array indexes as keys and timestamps as values, plus a weighted sort. It just seemed too complicated for the job I was trying to do... not anything I could point to code-wise, just a sense of "dammit, I know there's got to be a more graceful way to do this - this is just too fiddly!"

Your idea, and what I did here - only using a portion of the array - would have worked better than my original implementation, though. That one still came up with occasional doubles, or "too-near"s.

-- 
Human history becomes more and more a race between education and catastrophe. -- HG Wells

That could cause a brain hemorrhage!

The simplest solution I found to the OP issue was to divide the track list in two halves, then play each one of them alternately:

## pseudocode
my @list = shuffle get_tracks;
my @list1 = @list[0..@list/2-1];
my @list2 = @list[@list/2..$#list];
while (1) {
    play @list1;
    play @list2;
    shuffle @list1;
    shuffle @list2;
}
[download]

Regarding this:

Now, how you gonna make sure that NIN isn't followed by Elton John.

I have thought about a database with style tags and a mechanism for specifying which styles are allowable after a given song:

## pseudocode
my @style_levels = (
    [ qw/noise/               ],
    [ qw/metal heavy/         ],
    [ qw/pop rock/            ],
    [ qw/chill_out classical/ ],
);
sub get_next_song {
    my $cur_song = shift;
    my $cur_style = get_style_from_db $cur_song;  ## now we have 'pop'
+, 'classical'...
    my $index = get_index $cur_style;             ## walk @style_level
+s and return the index where 'pop' or 'classical' has been found
    my $next_index = $index + (-1,0,1)[rand 3];   ## randomly go to ne
+xt, current or previous style level (TODO: bounds checking)
    my $next_style = ${ $style_levels[$next_index] }[ rand @{$style_le
+vels[$next_index]} ];  ## choose a style of this level
    return get_song { style => $next_style };     ## pick some song of
+ this style
}
[download]

--
David Serrano

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.