Which two lists? ;)

I think you got it. :) I was, of course, speaking of any two successive lists resulting from the shuffling.

The randomizing approach I mentioned in my response to jethro would deal with that, though. Here's a shot at it in code:

#!/usr/bin/perl -w
use strict;
use List::Util qw[ shuffle ];

my @tracks = 1..100;
my $range = 5;  # No overlap for this number of songs

{
    my @last;
    for (@tracks){
        unshift @last, $_;
        @last = @last[0..4] if @last > 5;
        # Play it!
        print "$_\n";
    }
    my %h;
    do {
        # print "Shuffling...\n";
        @tracks = shuffle @tracks;
        @h{@last,@tracks[0..4]} = (1) x $range * 2;
    } while keys %h < $range * 2;

    # For demo purposes...
    sleep 5;
    redo;
}
[download]

The repeated shuffling mechanism kicks off a lot if $range is close to @tracks / 2; that makes for a good test.

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