Ok, those of you who have never taken any proper CS theory, go read the following:
http://dev.netcetera.org/blog/2007/08/24/good-knuth-bad-knuth/ Basically, since switching to mpd in the house, I noticed mpd's random shuffle was irritatingly bad and biased towards certain songs, so I read the code - Sure enough, mpd's song randomization is a flawed Knuth Shuffle, meaning that the shuffled array is not shuffled uniformly. It's a very common implementation mistake, good thing people writing mp3 playing daemons aren't writing crypto. The patch below to ports/audio/mpd puts a patch in that makes it use a correct Knuth, also known as a Fisher Yates shuffle (wikipedia will explain it to you) Someone please have a look, and either commit it or tell me to. -Bob ----8<---- Index: patch-src_playlist_c =================================================================== RCS file: patch-src_playlist_c diff -N patch-src_playlist_c --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ patch-src_playlist_c 5 Apr 2009 18:27:42 -0000 @@ -0,0 +1,57 @@ +--- src/playlist.c.orig Sun Apr 5 12:11:54 2009 ++++ src/playlist.c Sun Apr 5 12:06:13 2009 +@@ -1189,15 +1189,23 @@ + } + } + +- for (i = start; i <= end; i++) { +- ri = random() % (end - start + 1) + start; +- if (ri == playlist.current) +- playlist.current = i; +- else if (i == playlist.current) +- playlist.current = ri; +- swapOrder(i, ri); ++ /* ++ * Shuffle the Order. ++ * Use an unbiased Fisher-Yates shuffle. ++ */ ++ i = end + 1; ++ while (i > start + 1) { ++ ri = random() % (i - start); /* 0 <= ri <= len */ ++ ri += start; ++ i--; /* i is now the last pertinent index */ ++ if (i != ri) { /* do nothing if i == ri */ ++ if (ri == playlist.current) ++ playlist.current = i; ++ else if (i == playlist.current) ++ playlist.current = ri; ++ swapOrder(i, ri); ++ } + } +- + } + + int setPlaylistRandomStatus(int fd, int status) +@@ -1281,12 +1289,17 @@ + i = 0; + playlist.current = -1; + } +- /* shuffle the rest of the list */ +- for (; i < playlist.length; i++) { +- ri = random() % (playlist.length - 1) + 1; +- swapSongs(i, ri); ++ /* ++ * shuffle the rest of the list ++ * Use an unbiased Fisher-Yates shuffle. ++ */ ++ i = playlist.length; ++ while (i > 1) { ++ ri = random() % i; /* 0 <= ri <= len */ ++ i--; /* i is now the last pertinent index */ ++ if (i != ri) /* do nothing if i == ri */ ++ swapSongs(i, ri); + } +- + incrPlaylistVersion(); + } +
