12

I have a huge music playlist and, while some artists have many albums, others have just one song. I wanted to sort the playlist so the same artist won't play twice in a row, or his songs won't end up mostly in the beginning or end of the playlist.

Example playlist:

$ cat /tmp/playlist.m3u
Anna A. - Song 1
Anna A. - Song 2
I--Rock - Song 1
John B. - Song 1
John B. - Song 2
John B. - Song 3
John B. - Song 4
John B. - Song 5
Kyle C. - Song 1
U--Rock - Song 1

Output from sort -R or shuf:

$ sort -R /tmp/playlist.m3u
Anna A. - Song 1 #
U--Rock - Song 1
Anna A. - Song 2 # Anna's songs are all in the beginning.
John B. - Song 2
I--Rock - Song 1
John B. - Song 1
Kyle C. - Song 1
John B. - Song 4 #
John B. - Song 3 #
John B. - Song 5 # Three of John's songs in a row.

What I am expecting:

$ some_command /tmp/playlist.m3u
John B. - Song 1
Anna A. - Song 1
John B. - Song 2
I--Rock - Song 1
John B. - Song 3
Kyle C. - Song 1
Anna A. - Song 2
John B. - Song 4
U--Rock - Song 1
John B. - Song 5
10
  • 13
    Technically, what you are asking for is less randomness, and more structure. It's not impossible, but it will require a (bash/awk/perl/python/etc) script.
    – goldilocks
    Commented Nov 1, 2013 at 16:58
  • Or a structured randomness :) Commented Nov 1, 2013 at 17:12
  • Exactly! This would be a good exercise in perl or python. I think it would be a headache with bash, although it might work well with awk -- I don't know awk well enough to say.
    – goldilocks
    Commented Nov 1, 2013 at 17:51
  • Since there doesn't seem to be any tools to do that, a script seems to be the way to go. It's not that I'm lazy, but I'm out of ideas. Commented Nov 1, 2013 at 18:01
  • 1
    You might be able to do this with a simple algorithm: make the playlist by selecting a random song by each artist in turn (where the turn can be randomized too but without artist repetition). When all songs by one artist have been exhausted, start interleaving songs by the remaining artists (again, alternating among them in turn) with the existing playlist in such a way as to minimize adjacency of songs by the same artist. Keep repeating until you're done. I'm sorry that I have no time to pan this out into an actual script; I just thought it might be useful to help you roll your own.
    – Joseph R.
    Commented Nov 1, 2013 at 22:19

4 Answers 4

7
+50

Your example data and constraints actually only allow a few solutions—you must play John B. every other song, for example. I'm going to assume your actual full playlist isn't essentially John B, with random other stuff to break it up.

This is another random approach. Unlike @frostschutz's solution, it runs quickly. It does not guarantee a result that matches your criteria, however. I also present a second approach, which works on your example data—but I suspect will produce bad results on your real data. Having your real data (obfuscated), I add approach 3—which is a uniform random, except it avoids two songs by the same artist in a row. Note that it only makes 5 "draws" into the "deck" of remaining songs, if after that it still is faced with a duplicate artist, it'll output that song anyway—this way, its guaranteed that the program will actually finish.

Approach 1

Basically, it generates a playlist by at each point, asking "which artists do I still have unplayed songs from?" Then picking a random artist, and finally a random song from that artist. (That is, each artist is weighted equally, not in proportion to the number of songs.)

Give it a try on your actual playlist, and see if it produces better results than uniformly random.

Usage: ./script-file < input.m3u > output.m3u Make sure to chmod +x it, of course. Note it doesn't handle the signature line that is at the top of some M3U files properly... but your example didn't have that.

#!/usr/bin/perl
use warnings qw(all);
use strict;

use List::Util qw(shuffle);

# split the input playlist by artist
my %by_artist;
while (defined(my $line = <>)) {
    my $artist = ($line =~ /^(.+?) - /)
        ? $1
        : 'UNKNOWN';
    push @{$by_artist{$artist}}, $line;
}

# sort each artist's songs randomly
foreach my $l (values %by_artist) {
    @$l = shuffle @$l;
}

# pick a random artist, spit out their "last" (remeber: in random order)
# song, remove from the list. If empty, remove artist. Repeat until no
# artists left.
while (%by_artist) {
    my @a_avail = keys %by_artist;
    my $a = $a_avail[int rand @a_avail];
    my $songs = $by_artist{$a};
    print pop @$songs;
    @$songs or delete $by_artist{$a};
}

Approach 2

As a second approach, instead of pick a random artist, you can use pick the artist with the most songs, who is also not the last artist we picked. The final paragraph of the program then becomes:

# pick the artist with the most songs who isn't the last artist, spit
# out their "last" (remeber: in random order) song, remove from the
# list. If empty, remove artist. Repeat until no artists left.
my $last_a;
while (%by_artist) {
    my %counts = map { $_, scalar(@{$by_artist{$_}}) } keys %by_artist;
    my @sorted = sort { $counts{$b} <=> $counts{$a} } shuffle keys %by_artist;
    my $a = (1 == @sorted)
        ? $sorted[0]
        : (defined $last_a && $last_a eq $sorted[0])
            ? $sorted[1]
            : $sorted[0];
    $last_a = $a;
    my $songs = $by_artist{$a};
    print pop @$songs;
    @$songs or delete $by_artist{$a};
}

The rest of the program stays the same. Note that this by far isn't the most efficient way to do this, but it should be fast enough for playlists of any sane size. With your example data, all generated playlists will start with a John B. song, then an Anna A. song, then a John B. song. After that, it's much less predictable (as everyone but John B. has one song left). Note that this assumes Perl 5.7 or later.

Approach 3

Usage is the same as the previous 2. Note the 0..4 part, that's where the 5 tries max comes from. You could up the number of tries, e.g., 0..9 would give 10 total. (0..4 = 0, 1, 2, 3, 4, which you'll notice is actually 5 items).

#!/usr/bin/perl
use warnings qw(all);
use strict;

# read in playlist
my @songs = <>;

# Pick one randomly. Check if its the same artist as the previous song.
# If it is, try another random one. Try again 4 times (5 total). If its
# still the same, accept it anyway.
my $last_artist;
while (@songs) {
    my ($song_idx, $artist);
    for (0..4) {
        $song_idx = int rand @songs;
        $songs[$song_idx] =~ /^(.+?) - /;
        $artist = $1;
        last unless defined $last_artist;
        last unless defined $artist; # assume unknown are all different
        last if $last_artist ne $artist;
    }

    $last_artist = $artist;
    print splice(@songs, $song_idx, 1);
}
9
  • @TeresaeJunior did you try the two programs on the actual data, and see if either is to your liking? (And, wow, looking at that, it is very "Fhk Hhck" heavy... I'm going to add an approach 3)
    – derobert
    Commented Nov 4, 2013 at 17:45
  • Some artists actually do play twice in a row (you can check it with sed 's/ - .*//' output.m3u | uniq -d). And could you please explain if it takes care of some artists not ending up in the beginning or end of the playlist? Commented Nov 4, 2013 at 17:50
  • Approach 1 does indeed allow two (or more) in a row. Approach 2 does not. Approach 3 (about to edit it in) also does not (well, mostly). Approach 2 definitely weights the beginning of the playlist by the most-common artists. Approach 3 will not.
    – derobert
    Commented Nov 4, 2013 at 17:52
  • 1
    @TeresaeJunior I'm glad the third one worked! I'm not sure exactly what approach 4 would have been, but it'd be scary...
    – derobert
    Commented Nov 4, 2013 at 18:29
  • 1
    @JosephR. Approach #3 does use the number of songs by each artist as a weight—implicitly, by picking a random song. The more songs an artist has, the more likely that artist is to be picked. #1 is the only one that does not weight by number of songs.
    – derobert
    Commented Nov 4, 2013 at 21:33
5

If I had to apply that shuffling to a deck of playing card, I think I'd first shuffle the deck, then display the cards in a row before my eyes and processing from left to right, wherever there are adjacent clubs or heart... move all but one of those at random somewhere else (though not next to another one of the same type).

For example, with a hand like

🂡 🂢 🂣 🂤 🂥 🂦 🂧 🂨 🂱 🂲 🂳 🃁 🃂 🃃 🃑 🃒

After basic shuffling:

🂣 🃑 🂲 🂦 🂳 🃁<🂧 🂡 🂨>🃂<🂤 🂢>🃃 🂱 🂥 🃒
                   1  2       3

two groups of adjacent spades, we need to relocate 1, 2 and 3. For 1, the choices are:

🂣 🃑 🂲 🂦 🂳 🃁 🂧 🂡 🂨 🃂 🂤 🂢 🃃 🂱 🂥 🃒
    ↑        ↑                    ↑        ↑

We pick one at random from those 4. Then we repeat the process for 2 and 3.

Implemented in perl that would be:

shuf list | perl -e '
  @songs = map {/(.*?)-/; [$1,$_]} <>;
  for ($i = 0; $i < @songs; $i++) {
    if (($author = $songs[$i]->[0]) eq $previous) {
      my @reloc_candidates, $same;
      for($j = 0; $j < @songs; $j++) {
        # build a list of positions where we could move that song to
        if ($songs[$j]->[0] eq $author) {$same = 1} else {
          push @reloc_candidates, $j unless $same;
          $same = 0;
        }
      }
      push @reloc_candidates, $j unless $same;

      if (@reloc_candidates) {
        # now pick one of them at random:
        my $chosen = $reloc_candidates[int(rand(@reloc_candidates))];
        splice @songs, $chosen - ($chosen > $i), 0, splice @songs, $i, 1;
        $i -= $chosen > $i;
      }
    }
    $previous = $author;
  }
  print map {$_->[1]} @songs'

It will find a solution with non-adjacent artists if it exists (unless more than half the songs are from the same artist), and should be uniform AFAICT.

1
  • Upon trying the three different scripts (perl and bash), all of them shuffle the playlist I left on pastebin without leaving adjacent songs, but yours seem to do it in a more smart way. Besides, only yours works perfectly on the John B. example, which undoubtedly makes it for a best answer. I promised derobert to accept his answer, since he was so patient and helpful to me, and his 3rd approach is very good too. So I'll give you the best answer and the bounty to him, and I hope he doesn't get angry at me :) Commented Nov 5, 2013 at 23:55
2

If you don't mind it being horribly inefficient...

while [ 1 ]
do
    R="`shuf playlist`"
    D="`echo "$R" | sed -e 's/ - .*//' | uniq -c -d`"
    if [ "$D" == "" ]
    then
        break
    #else # DEBUG ONLY:
    #    echo --- FAIL: ---
    #    echo "$D"
    #    echo -------------
    fi
done

echo "$R"

It just keeps rolling and rolling until it comes upon a result that does not have two or more Johns in a row. If there are so many Johns in your playlist that such a combination does not exist or extremely unlikely to be rolled, well, it will hang.

Example result with your input:

John B. - Song 4
Kyle C. - Song 1
Anna A. - Song 2
John B. - Song 3
Anna A. - Song 1
John B. - Song 1
U--Rock - Song 1
John B. - Song 2
I--Rock - Song 1
John B. - Song 5

If you uncomment the debug lines, it will tell you why it failed:

--- FAIL: ---
      3 John B.
-------------
--- FAIL: ---
      2 John B.
      2 John B.
-------------

That should help determine the cause in case it hangs indefinitely.

4
  • I like the idea, but the script's been running for almost 15m and couldn't find a suitable combination. It is not that I have too many songs by John, but the playlist is more than 7000 lines, and it seems to be how sort is designed. Commented Nov 1, 2013 at 19:53
  • 1
    Regarding performance, shuf shuffles the playlist 80 times faster than sort -R. I didn't know that either! I'll leave it running for 15 minutes with shuf, the chances are higher! Commented Nov 1, 2013 at 19:57
  • To debug, echo "$D" before the if. That should tell you which duplicates prevented the result from being chosen. That should tell you where to look for the problem. (Edit: Added possible debug code to the answer.) Commented Nov 1, 2013 at 20:07
  • DEBUG always shows about 100 lines, but from random artists, so it seems a lot of artists are causing the problem. I think it is not really possible with sort or shuf. Commented Nov 1, 2013 at 20:24
1

Another approach using Bash. It reads the playlist in random order, tries to insert the line at the other end of the list if it's a duplicate, and puts a single dupe aside to reinsert it in another place. It fails if there are triple duplicates (first, last, and set aside identical) and it will append those bad entries to the very end of the list. It seems to be able to solve the extensive list you uploaded most of the time.

#!/bin/bash

first_artist=''
last_artist=''
bad_artist=''
bad_line=''
result=''
bad_result=''

while read line
do
    artist=${line/ - */}
    line="$line"$'\n'

    if [ "$artist" != "$first_artist" ]
    then
        result="$line""$result"
        first_artist="$artist"

        # special case: first = last
        if [ "$last_artist" == '' ]
        then
            last_artist="$artist"
        fi

        # try reinserting bad
        if [ "$bad_artist" != '' -a "$bad_artist" != "$first_artist" ]
        then
            first_artist="$bad_artist"
            result="$bad_line""$result"
            bad_artist=''
            bad_line=''
        fi
    elif [ "$artist" != "$last_artist" ]
    then
        result="$result""$line"
        last_artist="$artist"

        # try reinserting bad
        if [ "$bad_artist" != '' -a "$bad_artist" != "$last_artist" ]
        then
            last_artist="$bad_artist"
            result="$result""$bad_line"
            bad_artist=''
            bad_line=''
        fi
    else
        if [ "$bad_artist" == '' ]
        then
            bad_artist="$artist"
            bad_line="$line"
        else
            # first, last and bad are the same artist :(
            bad_result="$bad_result""$line"
        fi
    fi
done < <(shuf playlist)

# leftovers?
if [ "$bad_artist" != '' ]
then
    bad_result="$bad_result""$bad_line"
fi

echo -n "$result"
echo -n "$bad_result"

It could be smarter... in your John example, John will usually stick to being the last_artist because it always tries to append the first_artist first. So if it gets two other artists in between, it's not smart enough to append one to the beginning and the other to the end to avoid the triple-John. So with lists that basically require every other artist to be John, you get more failures than you should.

1
  • Thank you for this bash script. It is the only one I can really understand and modify at will! Commented Nov 5, 2013 at 23:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .