Javascript Weighted Random Number Generation

Question

I have an array that looks something like this:

[ { plays: 0, otherData: someValues }, { plays: 4, otherData: someValues }, { plays: 1, otherData: someValues }, { plays: 2, otherData: someValues } { plays: 9, otherData: someValues }, { plays: 7, otherData: someValues }, { plays: 5, otherData: someValues }, { plays: 0, otherData: someValues }, { plays: 8, otherData: someValues } ] 

This is an array of information about the songs in the playlist, where plays is the number of times the song was played. I am trying to come up with a weighted random number generator that will select an index of an element weighted in such a way that less reproducible songs are more likely to be selected. Here is the code that I have now:

 function pickRandom(){ var oldIndex = index; if(songs.length <= 1) return index = 0; var unheard = []; for(i in songs){ if(!songs[i].plays) unheard.push(i); }if(unheard.length > 0) return index = unheard[Math.round(Math.random() * (unheard.length - 1))]; var tries = 0; while(index == oldIndex && tries < 100){ index = Math.round(Math.random() * (songs.length - 1)); tries++; }return index; } 

There are a number of things in this decision that I am unhappy with. Firstly, he is not weighed as much as he simply chooses an unplayable song or any old random one, if everything in the array was played at least once. Secondly, it creates a new array, and since there are sometimes hundreds of songs in playlists, I would like to brush it off as soon as possible.

The closest solution I could come up with is to copy each element to a new array several times based on its plays value, and then select an element from this, but this exacerbates the problem of creating a new array, since this second array can easily reach thousands of elements. I would be very grateful for any help or suggestions; even pseudo code will be fine.

Answer 1

I would do what you want to do with loops. Summarize the maximum number of plays for any song in the list, then change the probability by calculating a number that has an inverse weight and choose from the total. Something like that:

 function pickRandom(myArray) { var maxPlays = 0, reverseTotPlays = 0, ipl, picked, revAcc = 0; // Empty array or bad input param if (!myArray || !myArray.length) { return -1; } // Calculate the max plays for any song in the list for (ipl = 0; ipl < myArray.length; ++ipl) { if (myArray[ipl].plays > maxPlays) { maxPlays = myArray[ipl].plays; } } maxPlays += 1; // Avoid excluding max songs // Calculate the reverse weighted total plays for (ipl = 0; ipl < myArray.length; ++ipl) { reverseTotPlays += maxPlays - myArray[ipl].plays; } // Choose a random number over the reverse weighted spectrum picked = ~~(Math.random() * reverseTotPlays); // Find which array member the random number belongs to for (ipl = 0; ipl < myArray.length; ++ipl) { revAcc += maxPlays - myArray[ipl].plays; if (revAcc > picked) { return ipl; } } return myArray.length - 1; } var pp = [{ plays: 3 }, { plays: 1 }, { plays: 2 }]; console.log(pickRandom(pp)); 

Working JSFiddle Here

Change If you do not want to have zero probability when playing songs that have been played, the maximum number of times in the list, add +1 to maxPlays after the first cycle.

Answer 2

Probably the easiest way is to make a two-stage choice, start by choosing a random song, and then see if this song passes in the second test, designed to select less played songs preferable. If this second test fails, drop it and start the whole process again.

Example (excuse me if I made a mistake, it was a long time ago, since I did some javascript):

 function pickRandom(){ var candidate; while (true){ candidate = songs[Math.round(Math.random() * (songs.length - 1))]; //largest_played is the largest number of plays of any one song // I've magiced it out of nowhere here, find it in a manner that // suits your program. if ( candidate.plays/largest_played < math.random() ){ return candidate; } } } 

Obviously there are no errors in brilliance and no errors, but this should be enough to get you started.