Getting Random Number with probability

Question

While trying to make a Audio Player , currently working at Playlist ,and i have problem's with shuffle function .

First i have a list with file names within:

List<string> myPlaylist = new List<string>();
            myPlaylist.Add("Untitled1.mp3");
            myPlaylist.Add("Untitled2.mp3");
            myPlaylist.Add("Untitled3.mp3");

and than with this method im getting random item at playlist :

public string shuffleme(List<string> playlist)
        { 
            Random random = new Random();
            int playlistitem = random.Next(0,playlist.Count);
            return playlist[playlistitem];
        }

but i need to get random element based in some kind of probability ,let say i have 1-10 values which describes a Playlist Item priority so the Item with the Lowest Priority will have a better chance to be returned against the Item with the Higher priority ,so i need to get Random item with probability based on item priority .

score 4 · Accepted Answer · answered Nov 10 '11 at 08:05

4

What you can do is create a playlist in the following way:

Every high-priority item, place it 3x in the list.
Every mid-priority item, place it 2x in the list.
All other items, place them 1x in the list.
Shuffle the list.
Verify that no song appears twice in a row; if you find one that does (say, at locations 11 and 12), simply swap the second one with the next one in the list (i.e., as in this example, swap #12 with #13).

Then when it is time to select the next song, just pick the first one in the list, take it out and place it back in a random location in the 2nd half of the list.

That should do the trick!

answered Nov 10 '11 at 08:05

Roy Dictus

32,551
8
60
76

If you're going to ensure no two adjacent positions are the same song in your original shuffle, you'll probably want to do that when inserting a song into the back half of the list as well. Other than that very minor hole, not a bad idea. – paxdiablo Nov 10 '11 at 08:13
@paxdiablo True, I forgot to mention that. Another option would be to just put the song back at the end of the list; that would not require another check but of course it keeps the order which may not be what you want... – Roy Dictus Nov 10 '11 at 08:18

score 2 · Answer 2 · edited May 23 '17 at 10:34

2

The accepted answer to this SO question has pseudo-code that is easily portable to C#. It also talks about how to optimize for rarely-changing weights and/or large lists, both of which I would expect to apply to an audio player.

edited May 23 '17 at 10:34

Community

1
1

answered Nov 10 '11 at 08:06

DocMax

12,094
7
44
44

score 1 · Answer 3 · answered Nov 10 '11 at 08:16

There is priority (the greater integer the higher priority) added in the list for each item and also sum of all priorities in the list as a parameter, as it is good to have it cached.

   public string shuffleme(List<Tuple<string,int> playlist, int prioritiesSum)
   { 
      Random random = new Random();

      foreach(var song in playlist)
      {
         var prob=random.NextDouble(); //0.0-1.0
         if (prob < song.Item2/(double)prioritiesSum)
            return song.Item1;
         else
            prioritiesSum-=song.Item2;
      }
   }

score 0 · Answer 4 · answered Nov 10 '11 at 08:26

Ok so what you need is a weighted random system.

One technique is to simulate a wheel (like in TV show games). You place each item on that wheel, the space taken by each item is proportional to its importance. Then you virtually spin that wheel so the most important items have greater chance to be selected.

Let's assume that your priority is based on the number P which is how many times the song was played before.

Place all your songs in an array-like structure
Calculate the perimeter of the wheel
It would be the sum of all the P values
Generate a random number R in the range [0; P]
Loop over the array and at every iteration:
- The current position on the wheel: C += P
- Test if R >= C
  If True then select the song else go to the next song

By doing so the song which has been played the most has more chance to be selected.

Getting Random Number with probability

4 Answers4