How can I get weighted random selections from an array in Perl?

Question

I need to random some elements from an array. I'm doing that by randomizing the index $array[int(rand(100))]. I want some of the elements to appear more often. How do I do it?

I thought of a stupid solution of having those elements duplicated several times in the array, but I'm sure you guys can do better.

Answer 1

You want to generate a weighted random sample. The linked question covers both with and without replacement.

Answer 2

Seems that a rather natural way involves setting up a binary search. Let's say a bunch of people are enrolled in a raffle, where people are allowed to submit their names as many times as they want. We have the following names with the following number of submissions:

• Juliet: 2
• Jenny: 11
• Jessica: 7
• Jan: 1
• Jane: 1
• Jean: 5

Now if we want to randomly select a name out of the bag, we just assign each name a range starting from 0:

• Juliet: 0, 1
• Jenny: 2, 12
• Jessica: 13, 19
• Jan: 20, 20
• Jane: 21, 21
• Jean: 22, 26

Alright, so we have an array of adjacent ranges, were each range is between 0 and 26. We use a modified binary search to find our target item (pseudocode):

let raffle := { Juliet: 0, 1;
                Jenny: 2, 12;
                Jessica: 13, 19;
                Jan: 20, 20;
                Jane: 21, 21;
                Jean: 22, 26 }

let search minIndex maxIndex rangeValue =
    if minIndex > maxIndex then
        failwith "Not found"

    let selectedIndex = (minIndex + maxIndex) / 2
    let item = raffle[selectedIndex]

    if item.range.min >= rangeValue && item.range.max <= rangeValue
        return item.name
    elif item.range.min < rangeValue
        return search minIndex (selectedIndex - 1) rangeValue
    else
        return search (selectedIndex + 1) maxIndex rangeValue