Get random object from percent list

Question

I cannot find an effective way to select a random object by the percentage of each object.

Basically, I give the method a map of objects and the likelihood that this object will be selected. Preferably, I want it to have many decimal places, as the longest, but one decimal place is also good.

public static <T> T random(Map<T, Double> chances) {
    T toReturn = null;
    double rand = new Random().nextInt(1000) / 10.0D;

    // ???

    return toReturn;
}

Thanks in advance.

Answer 1

The main strategy:

• Calculate a random percentage of Rand from 0% inclusive to 100 exclusive%
• Iterate through MapSetSet
• For each record, if the value is less than Rand, Return Key
• Otherwise, add the value to Rand and continue

Answer 2

( 100), , :

public static <T> T getRandomItem(Map<T, Double> chances) {
    double chance = random.nextDouble() * 100.0;
    double cumulative = 0.0;
    for (T item: chances.keySet()) {
        cumulative += chances.get(item);
        if (chance < cumulative)
            return item;
    }
    throw new IllegalStateException("chances don't sum to 100");
}

Answer 3

" ", ( ) wikipedia.

Answer 4

. , 0,1, 0,3, 0,2, 0,1, 0,3. A A = [0,1, 0,4, 0,6, 0,7, 1,0], A [n] = A [n-1] + p_n, n > 0 A [0] = p_0, p_n - n. r x A, , A [x] > r, x - .

:

cumulative_chances = [chances[0]]
for i=1 to chances.size()
    cumulative_chances.append(chances[i]+cumulative_chances[i-1])
r=random(0, cumulative_chances.last())
i=0
while cumulative_chances[i]<r
   i++
return i

, , p_n > 0 n. , , .

If nothing in your applications is performance sensitive, you can do this calculation inside a function. In other cases, I tentatively calculated it. Note that pseudo-code is not sensitive to normalization of values. They don't need to add upp to 1 (or 100 if you want a percentage), it works anyway.

Answer 5

I did what Patrick Parker told me to do, and it works great! Many thanks.

public static <T> T random(CustomMap<T, Double> map) {
    double rand = (double) new Random().nextInt(10000001) / 100000.0D;
    double total = 0.0D;

    for (T t : map.getKeys()) {
        double chance = map.get(t);
        total += chance;

        if (total >= rand) return t;
    }

    return null;
}