Weighted random number generation in Javascript

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
    }
]

It's an array of information about songs in a playlist, where plays is the number of times a song has been played. I' trying to come up with a weighted random number generator that will pick an index of an element, weighted such that less-played songs are more likely to be picked. Here's the code 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 with this solution that I'm unhappy with. First off, it's not weighted so much as it really just picks an unplayed song, or any old random one if everything in the array has been played at least once. Second, it creates a new array, and since playlists will sometimes have hundreds of songs, that's something I'd like to steer away from if possible.

The closest solution I've been able to come up with is copying each element into a new array multiple times based on its plays value, then pick an element out of that, but that worsens the issue of creating a new array, since that second array could easily reach thousands of elements. I'd be much appreciative of any help or suggestions; even pseudocode would be fine.

Answer 1

I would do what you want to do with loops. Total up the max number of plays for any song in the list, then reverse the probability by calculating a number that is reverse weighted and choosing from the reverse total. Something like this:

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

Edit: If you don't want a zero probability on playing the songs that have been played the max times in the list, add +1 to maxPlays after the first loop.

Answer 2

It's probably easiest to do a two-step selection, start by selecting a random song, then see if that song passes a second test designed to preferentially select less-played songs. If it fails that second test, discard it and start the whole process again.

An example (forgive me if I've made a mistake, it's been a long time since I did any 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's a lot of gloss and error checking missing, but it should be enough to get you started.