I have the following Hashmap:
Map <Country, List<City>> map = new HashMap<Country, List<City>>();
I want to pick a group of countries at random, with the following condition: Countries with a lower number of cities should have a higher probability of being selected.
To tackle this I thought I would create the following map:
Map <Country, Integer> map = new HashMap<Country, Integer>();
Where the integer represents the size of List<City>
.
This is so that I can then sort the Map
based on the Integer value and then select countries with low Integer values.
But it seems like I am doing this in a very long way, plus it is not very random. Do you have any suggestions on how to solve this problem efficiently?
There is a parallel here with the technique used in genetic algorithm called the roulette wheel selection.
It is pretty simple to implement :
The countries will be picked with a probability equal to their number of cities
EDIT : if the number of cities is very large, you can normalize the numbers by dividing by the lowest cities count, so that each country remains present in the table.