---------------------------------------------
import java.util.*;
public class City {
String CityName;
int Population; //cumulative population
City (String S, int pop){
CityName = S;
Population = pop;
}
}
---------------------------------------------
import java.util.*;
class CityGenerator {
List
List
Random rGen;
int CurrentTotalPopulation;
int FinalTotalPopulation;
public CityGenerator(List Cities_List) {
Cities = Cities_List;
City CurrentCity;
rGen = new Random();
CumulativePops = new ArrayList
CurrentTotalPopulation = 0;
//Calculate the cumulative totals
for (City c : Cities){
CurrentCity = c;
CurrentTotalPopulation += CurrentCity.Population;
CumulativePops.add(CurrentTotalPopulation);
}
FinalTotalPopulation = CurrentTotalPopulation;
}
public City getCity()
{
//runs in log(n) time as it uses a binary search
int randCumulativePop = rGen.nextInt(FinalTotalPopulation);
int cityIndex = Collections.binarySearch(CumulativePops,randCumulativePop);
//binarySearch returns minus one unless its an exact match
if(cityIndex < 0) {
cityIndex *= -1;
cityIndex -= 1;
}
City city = Cities.get(cityIndex);
return (city);
}
public String verifySample(int sampleSize)
{
int citycount = Cities.size();
int[] IncrementTotals = new int[citycount];
int CityIndex;
Integer count;
City C1, C2;
HashMap hm = new HashMap();
for(int i=0;i
count = (Integer)(hm.get(C1));
if (count == null) {hm.put(C1, 1);}
else {hm.put(C1,new Integer(count.intValue()+1)); }
}
String output = new String();
for(int j=0;j
output += C2.CityName + ": " + hm.get(C2) + "\n";
}
return output;
}
public static void CreateData (List Cities) {
Cities.add(new City("San Francisco", 20000));
Cities.add(new City("New York", 50000));
Cities.add(new City("Boston", 20000));
Cities.add(new City("Toronto", 7500));
Cities.add(new City("Cambridge", 2500));
}
public static void main(String[] args) {
List
CreateData(Cities); //Add sample data
CityGenerator cGen = new CityGenerator(Cities);
System.out.println(cGen.verifySample(100000)); //Verify with large test run
}
}
Here's a brief summary of what's happening. Define a class City that associates each cities name with its population, and create a List of all the cities in your sample data. Pass this to the constructor of CityGenerator, and use it to build a second list of cumulative totals. From here, all the action happens in the getCity() method. In this method, we generate a random number between 1 and the final total population, then we do a binary search on our list of cumulative totals to pull out a random city name. This approach gives us each city name with a proability that is proportional to its population over total population of all the cities, which was the requirement. The method verifySample() simply runs a high volume of tests, and stores all the results in a frequency table, implemented via a HashMap.
