Index: shell/rb-playlist-manager.c
===================================================================
--- shell/rb-playlist-manager.c	(revision 7)
+++ shell/rb-playlist-manager.c	(working copy)
@@ -74,6 +74,8 @@
 						  RBPlaylistManager *mgr);
 static void rb_playlist_manager_cmd_new_automatic_playlist (GtkAction *action,
 							    RBPlaylistManager *mgr);
+static void rb_playlist_manager_cmd_shuffle_playlist (GtkAction *action,
+						      RBPlaylistManager *mgr);
 static void rb_playlist_manager_cmd_rename_playlist (GtkAction *action,
 						     RBPlaylistManager *mgr);
 static void rb_playlist_manager_cmd_delete_playlist (GtkAction *action,
@@ -154,6 +156,9 @@
 	{ "QueuePlaylist", NULL, N_("_Queue All Tracks"), NULL,
 	  N_("Add all tracks in this playlist to the queue"),
 	  G_CALLBACK (rb_playlist_manager_cmd_queue_playlist) },
+	{ "ShufflePlaylist", NULL, N_("_Shuffle Playlist"), NULL,
+	  N_("Shuffle the tracks in this playlist"),
+	  G_CALLBACK (rb_playlist_manager_cmd_shuffle_playlist) },
 };
 static guint rb_playlist_manager_n_actions = G_N_ELEMENTS (rb_playlist_manager_actions);
 
@@ -1253,7 +1258,79 @@
 	g_object_unref (model);
 }
 
+
+static gboolean
+_count_track_cb (RhythmDBQueryModel *model,
+		 GtkTreePath *path,
+		 GtkTreeIter *iter,
+		 GList **retval)
+{
+	RhythmDBEntry *entry;
+
+	entry = rhythmdb_query_model_iter_to_entry (model, iter);
+	*retval = g_list_append(*retval, entry);
+
+	return FALSE;
+}
+
 static void
+_shuffle_track_cb (gpointer data,
+		 gpointer user_data)
+{
+	RhythmDBEntry *entry;
+	GList *passdata;
+
+	RBStaticPlaylistSource *playlist_source;
+	int numtracks;
+	int new_location;
+
+	entry = (RhythmDBEntry *)data;
+	passdata = (GList *)passdata;
+
+	playlist_source = (RBStaticPlaylistSource *)g_list_nth_data (passdata, 0);
+	numtracks = *(int *)(g_list_nth_data (passdata, 1));
+
+	new_location = g_random_int_range (0, numtracks);
+
+	rb_static_playlist_source_move_entry (playlist_source, entry, 
+						new_location);
+	rhythmdb_entry_unref (entry);
+}
+
+static void
+rb_playlist_manager_cmd_shuffle_playlist (GtkAction *action,
+					RBPlaylistManager *mgr)
+{
+	RhythmDBQueryModel *model;
+	int numtracks = 0;
+	GList *passdata;
+	GList *entries;
+
+	g_object_get (mgr->priv->selected_source, "query-model", &model, NULL);
+
+	/* Phase I:  Put the tracks into a list, so I can traverse while I 
+	 * move the entries around. */
+	entries = NULL;
+	gtk_tree_model_foreach (GTK_TREE_MODEL (model),
+				(GtkTreeModelForeachFunc) _count_track_cb,
+				&entries);
+
+	numtracks = g_list_length (entries);
+
+	/* Phase II:  Traverse the list, placing the entries in random places 
+	 * in the playlist. */
+	passdata = NULL;
+	passdata = g_list_append (passdata, mgr->priv->selected_source);
+	passdata = g_list_append (passdata, &numtracks);
+
+	g_list_foreach (entries, _shuffle_track_cb, passdata);
+
+	g_list_free (entries);
+	g_list_free (passdata);
+	g_object_unref (model);
+}
+
+static void
 rb_playlist_manager_cmd_rename_playlist (GtkAction *action,
 					 RBPlaylistManager *mgr)
 {
Index: data/ui/rhythmbox-ui.xml
===================================================================
--- data/ui/rhythmbox-ui.xml	(revision 7)
+++ data/ui/rhythmbox-ui.xml	(working copy)
@@ -222,6 +222,7 @@
     <menuitem name="RenameAutoPlaylistPopup" action="MusicPlaylistRenamePlaylist"/>
     <separator/>
     <menuitem name="QueuePlaylistPopup" action="QueuePlaylist"/>
+    <menuitem name="ShufflePlaylistPopup" action="ShufflePlaylist"/>
     <placeholder name="PlaylistSourcePopupPluginPlaceholder" />
     <separator/>
     <menuitem name="DeletePlaylistPopup" action="MusicPlaylistDeletePlaylist"/>
@@ -234,6 +235,7 @@
     <menuitem name="RenameAutoPlaylistPopup" action="MusicPlaylistRenamePlaylist"/>
     <separator/>
     <menuitem name="QueuePlaylistPopup" action="QueuePlaylist"/>
+    <menuitem name="ShufflePlaylistPopup" action="ShufflePlaylist"/>
     <placeholder name="AutoPlaylistSourcePopupPluginPlaceholder" />
     <separator/>
     <menuitem name="DeleteAutoPlaylistPopup" action="MusicPlaylistDeletePlaylist"/>
