1

As said in title, I would like to take a random element from a list using different "randomization factor". The context is as follows:

  • I have a list of classes, in which I don't know the number of classes.
  • All of the classes in this list extend a common superclass with a method returning a percentage of chance for them to be chosen in the list.

I may have an idea, like addition all the percentages of chance for the classes to appear and if it exceeds 100 %, divide each of the percentage so that the relative chances are still the same, but the total percentage does not exceed 100 %. It may not be very clear, if it isn't i'll explain a bit more.

3 Answers 3

5

Suppose you have 3 objects in the list, and these objects have a "percentage" (that you should really call "weight", since it's not a percentage) of 4, 7 and 9.

Sum all the weights: 20.

So the first element should be picked out 4 out of 20 times on average, the second one 7 out of 20, etc.

So, generate an integer between 0 and 20. If the result is between 0 and 4, pick the first element. If the result is between 4 and 11, pick the second one, and if the result is between 11 and 20, pick the last one.

The rest is just implementation details.

Sign up to request clarification or add additional context in comments.

1 Comment

That's exactly it ! I don't know how I forgot to think of something like that, thanks.
3

Just sum up the numbers, create a random value in [0, 1), mulitply by the sum and iterate through the list subtracting the numbers from the result until you get a number < 0:

List<MyClass> elements = ...
double sum = elements.stream().mapToDouble(MyClass::getChance).sum();
double rand = Math.random() * sum;
MyClass choice = null;
for (MyClass e : elements) {
    choice = e;
    rand -= e.getChance();
    if (rand < 0) {
        break;
    }
}

Comments

0

If you're just going to do the lookup once (or a few times), then the answer by @fabian is good.

If you however are going to do it a lot, then the sequential search performed by that solution is not efficient.

For a more efficient solution, you need a more directed lookup, so you need to organize the data by the cumulative chance. This can be done as an array using binary search, or as a NavigableMap keyed by the cumulative chance.

With a NavigableMap such as TreeMap, you can then use higherEntry(K key) to find the selected object:

Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.

So, here is sample code:

public class MyObj {
    private final String name;
    private final int weight;
    public MyObj(String name, int weight) {
        this.name = name;
        this.weight = weight;
    }
    public String getName() {
        return this.name;
    }
    public int getWeight() {
        return this.weight;
    }
    @Override
    public String toString() {
        return this.name;
    }

    public static void main(String[] args) {
        // Build list of objects
        List<MyObj> list = Arrays.asList(
                new MyObj("A", 2),
                new MyObj("B", 6),
                new MyObj("C", 12)
        );

        // Build map keyed by cumulative weight
        NavigableMap<Integer, MyObj> weighedMap = new TreeMap<>();
        int totalWeight = 0;
        for (MyObj obj : list) {
            totalWeight += obj.getWeight();
            weighedMap.put(totalWeight, obj);
        }
        System.out.println(weighedMap);

        // Pick 20 objects randomly according to weight
        Random rnd = new Random();
        for (int i = 0; i < 20; i++) {
            int pick = rnd.nextInt(totalWeight);
            MyObj obj = weighedMap.higherEntry(pick).getValue();
            System.out.printf("%2d: %s%n", pick, obj);
        }
    }
}

Sample Output

{2=A, 8=B, 20=C}
14: C
10: C
 9: C
 5: B
11: C
 3: B
 1: A
 0: A
 1: A
 7: B
 4: B
11: C
17: C
15: C
 4: B
16: C
 9: C
17: C
19: C
 2: B

1 Comment

Very well explained. However the answer of @JB Nizet fits my problem more, as I just have to initalize my classes with the total weight, define a "threshold" of weight for each class and then randomize.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.