smart shuffle

Here's a feature I've always wanted when using an audio player: shuffle the playlist so that all the songs from the same artist are as spread out as possible. You can try it out with the amarok player (apt-get users can click this link), after you've installed this script. Just right-click the playlist and choose Smart Shuffle -> Shuffle.

Here's the Ruby code that does the job, as long as the parameter to #smart_shuffle is an array containing elements that respond to #artist.

require 'utils'

def smart_shuffle playlist
  playlist.shuffle!
  groups = playlist.group_by {|item| item.artist}

  groups.inject([]) {|decorated_playlist, group|
    decorated_playlist + group.decorate {|item, index|
      every_n = playlist.length.to_f / group.length.to_f
      rank = every_n * (index + 1) - (every_n / 2.to_f)
    }
  }.sort_by_decoration.undecorate
end

Here's the file it depends on, utils.rb:

class Array
  def shuffle
    sort_by { rand }
  end

  def shuffle!
    self.replace shuffle
  end
end

module Enumerable
  def group_by &block
    groups = Hash.new(){|hash, key| hash[key] = []}
    each {|item|
      retval = block.call(item)
      retval = "Unknown" if retval == "" || retval.nil?
      groups[retval.to_sym] << item
    }
    groups.values
  end

  def decorate &block
    decorated = []
    each_with_index {|item, index|
      decorated << [block.call(item, index), item]
    }
    decorated
  end

  def sort_by_decoration
    sort {|this, that|
      this[0] <=> that[0]
    }
  end

  def undecorate
    map {|item| item[1]}
  end
end

I'm using a simple DSU algorithm where the decoration is given in those two lines:

every_n = playlist.length.to_f / group.length.to_f
rank = every_n * (index + 1) - (every_n / 2.to_f)

The variable every_n is the interval between two songs by the same artist -- a song from this artist should come back every n songs. I calculate the rank based on that, adding one to the index to prevent useless cancellation when it is zero. I subtracted (every_n / 2.to_f ) simply because it was giving me better results.