Index: rhythmdb/rhythmdb-query-model.c
===================================================================
--- rhythmdb/rhythmdb-query-model.c	(revision 5495)
+++ rhythmdb/rhythmdb-query-model.c	(working copy)
@@ -1490,6 +1490,56 @@
 }
 
 void
+rhythmdb_query_model_shuffle_entries (RhythmDBQueryModel *model)
+{
+	RhythmDBEntry **entries;
+	int listsize;
+	int i;
+	int swapwith;
+	RhythmDBEntry *entry;
+	GSequenceIter *iter;
+
+	/* These are used to emit the reorder signal. */
+	GtkTreePath *path;
+	GtkTreeIter tree_iter;
+	int *map_new_old;
+
+	/* Convert the entries list to an array, for fast lookups. */
+	listsize = g_sequence_get_length (model->priv->entries);
+	entries = (RhythmDBEntry **)malloc (sizeof(RhythmDBEntry *) * listsize);
+	map_new_old = (int *)malloc (sizeof(int) * listsize);
+	for (iter = g_sequence_get_begin_iter (model->priv->entries), i=0; !g_sequence_iter_is_end (iter); iter = g_sequence_iter_next (iter), i+=1) {
+		entries[i] = g_sequence_get (iter);
+	}
+
+	/* Shuffle the array. */
+	for (i=0; i<listsize; i++) {
+		swapwith = g_random_int_range (i, listsize);
+		map_new_old[swapwith] = i;
+		entry = entries[swapwith];
+		entries[swapwith] = entries[i];
+		entries[i] = entry;
+	}
+
+	/* Convert the array back into a sequence, rebuilding the reverse map. */
+	for (iter = g_sequence_get_begin_iter (model->priv->entries), i=0; !g_sequence_iter_is_end (iter); iter = g_sequence_iter_next (iter), i+=1) {
+		g_sequence_set (iter, (gpointer)entries[i]);
+		rhythmdb_entry_ref (entries[i]);
+		g_hash_table_remove (model->priv->reverse_map, entries[i]);
+		g_hash_table_insert (model->priv->reverse_map, entries[i], iter);
+	}
+
+	/* Emit reorder signals. */
+	gtk_tree_model_get_iter_first (GTK_TREE_MODEL (model), &tree_iter);
+	path = gtk_tree_model_get_path (GTK_TREE_MODEL (model), &tree_iter);
+	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (model), path, &tree_iter, map_new_old);
+	gtk_tree_path_free (path);
+
+	free (map_new_old);
+	free (entries);
+}
+
+void
 rhythmdb_query_model_move_entry (RhythmDBQueryModel *model,
 				 RhythmDBEntry *entry,
 				 gint index)
Index: rhythmdb/rhythmdb-query-model.h
===================================================================
--- rhythmdb/rhythmdb-query-model.h	(revision 5495)
+++ rhythmdb/rhythmdb-query-model.h	(working copy)
@@ -106,6 +106,8 @@
 gboolean		rhythmdb_query_model_remove_entry	(RhythmDBQueryModel *model,
 								 RhythmDBEntry *entry);
 
+void			rhythmdb_query_model_shuffle_entries 	(RhythmDBQueryModel *model);
+
 void			rhythmdb_query_model_move_entry 	(RhythmDBQueryModel *model,
 								 RhythmDBEntry *entry,
 								 gint index);
Index: sources/rb-playlist-source.c
===================================================================
--- sources/rb-playlist-source.c	(revision 5495)
+++ sources/rb-playlist-source.c	(working copy)
@@ -867,4 +867,3 @@
 
 	return TRUE;
 }
-
Index: sources/rb-static-playlist-source.c
===================================================================
--- sources/rb-static-playlist-source.c	(revision 5495)
+++ sources/rb-static-playlist-source.c	(working copy)
@@ -883,3 +883,13 @@
 
 	return 0;
 }
+
+void
+rb_static_playlist_source_shuffle_playlist(RBStaticPlaylistSource *source) 
+{
+	RBStaticPlaylistSourcePrivate *priv = RB_STATIC_PLAYLIST_SOURCE_GET_PRIVATE (source);
+
+	rhythmdb_query_model_shuffle_entries (priv->base_model);
+
+	rb_playlist_source_mark_dirty (RB_PLAYLIST_SOURCE (source));
+}
Index: sources/rb-static-playlist-source.h
===================================================================
--- sources/rb-static-playlist-source.h	(revision 5495)
+++ sources/rb-static-playlist-source.h	(working copy)
@@ -79,6 +79,7 @@
 void		rb_static_playlist_source_move_entry	(RBStaticPlaylistSource *source,
 							 RhythmDBEntry *entry,
 							 gint index);
+void		rb_static_playlist_source_shuffle_playlist (RBStaticPlaylistSource *source);
 G_END_DECLS
 
 #endif /* __RB_STATIC_PLAYLIST_SOURCE_H */
Index: bindings/python/rhythmdb.defs
===================================================================
--- bindings/python/rhythmdb.defs	(revision 5495)
+++ bindings/python/rhythmdb.defs	(working copy)
@@ -843,6 +843,12 @@
   )
 )
 
+(define-method shuffle_entries
+  (of-object "RhythmDBQueryModel")
+  (c-name "rhythmdb_query_model_shuffle_entries")
+  (return-type "none")
+)
+
 (define-method move_entry
   (of-object "RhythmDBQueryModel")
   (c-name "rhythmdb_query_model_move_entry")
Index: shell/rb-playlist-manager.c
===================================================================
--- shell/rb-playlist-manager.c	(revision 5495)
+++ 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);
 
@@ -362,6 +367,7 @@
 	gboolean can_delete;
 	gboolean can_edit;
 	gboolean can_rename;
+	gboolean can_shuffle;
 	GtkAction *action;
 
 	party_mode = rb_shell_get_party_mode (mgr->priv->shell);
@@ -397,6 +403,11 @@
 	action = gtk_action_group_get_action (mgr->priv->actiongroup,
 					      "MusicPlaylistRenamePlaylist");
 	gtk_action_set_visible (action, can_rename);
+
+	can_shuffle = RB_IS_STATIC_PLAYLIST_SOURCE (mgr->priv->selected_source);
+	action = gtk_action_group_get_action (mgr->priv->actiongroup,
+					      "ShufflePlaylist");
+	gtk_action_set_sensitive (action, can_shuffle);
 }
 
 static void
@@ -1249,6 +1260,15 @@
 }
 
 static void
+rb_playlist_manager_cmd_shuffle_playlist (GtkAction *action,
+					RBPlaylistManager *mgr)
+{
+	RBStaticPlaylistSource *psource = RB_STATIC_PLAYLIST_SOURCE (mgr->priv->selected_source);
+
+	rb_static_playlist_source_shuffle_playlist(psource);
+}
+
+static void
 rb_playlist_manager_cmd_rename_playlist (GtkAction *action,
 					 RBPlaylistManager *mgr)
 {
Index: data/ui/rhythmbox-ui.xml
===================================================================
--- data/ui/rhythmbox-ui.xml	(revision 5495)
+++ 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"/>
