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.

Answer 2

I want to pick a group of countries with the lowest number of Cities.

Then you want a List of countries in order or number of cities. Why not create a Country class that contains a List of cities

public class Country{
   private final List<String> cityNames = new ArrayList<String>();
   private String name;
   public Country(String n) { name = n; }
   public void addCity(String name){ 
       cityNames.add(name);   // omitting validation
   }
   public List<String> getCityNames(){
       List<String> newList = new ArrayList<String>();
       newList.addAll(cityNames);
       return newList;
   }
   public int numberOfCities(){ 
       return cityNames.size(); 
   }

   public String getName() { return name; }

   @Override
   public String toString(){
      return name + ": Number of Cities = " + cityNames.size();
   }
}

Now you can sort a list of countries based on city count like this

... // inside some method

        Collections.sort(countries, new Comparator<Country>() {
        @Override
        public int compare(Country o1, Country o2) {
            if(o1.numberOfCities() < o2.numberOfCities()){
                return -1;
            }
            if(o1.numberOfCities() > o2.numberOfCities()){
                return 1;
            }
            return 0;
        }
    });

I just tested this with the following (NOTE: I added a "toString()" method to Country)

public static void main(String[] args) {
    Country usa = new Country("USA");
    Country canada = new Country("Canada");
    Country brazil = new Country("Brazil");
    usa.addCity("Lansing");
    usa.addCity("New York");
    usa.addCity("Los Angeles");
    usa.addCity("Houston");

    canada.addCity("Toronto");

    canada.addCity("Niagra");

    brazil.addCity("Vila Velha");
    brazil.addCity("Rio");
    brazil.addCity("Barbacena");

    List<Country> countries = new ArrayList<Country>();
    countries.add(usa);
    countries.add(brazil);
    countries.add(canada);
    System.out.println("\n\nAfter Sorting...");
    it = countries.iterator();
    while(it.hasNext()){
        System.out.println(it.next());
    }
    Collections.sort(countries, new Comparator<Country>() {
        @Override
        public int compare(Country o1, Country o2) {
            if(o1.numberOfCities() < o2.numberOfCities()){
                return -1;
            }
            if(o1.numberOfCities() > o2.numberOfCities()){
                return 1;
            }
            return 0;
        }
    });

    System.out.println("\n\nAfter Sorting...");
    it = countries.iterator();
    while(it.hasNext()){
        System.out.println(it.next());
    }

}

And the output

 Before sorting....
 USA: Number of Cities = 4
 Brazil: Number of Cities = 3
 Canada: Number of Cities = 2


 After Sorting...
 Canada: Number of Cities = 2
 Brazil: Number of Cities = 3
 USA: Number of Cities = 4