Randomly selecting a key based on the frequency of a value

Question

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?

Answer 1

There is a parallel here with the technique used in genetic algorithm called the roulette wheel selection.

It is pretty simple to implement :

1. Create an array of countries whom size is the total of integer for all the countries
2. Put each country N times in the array where N is the number of cities
3. Randomly select a value in the array

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.