3

我有以下哈希图： 

Map <Country, List<City>> map = new HashMap<Country, List<City>>();

我想随机选择一组国家，条件如下：城市数量较少的国家应该有更高的被选中的概率。

为了解决这个问题，我想我会创建以下地图： 

Map <Country, Integer> map = new HashMap<Country, Integer>();

其中整数表示 的大小List<City>。

这样我就可以Map根据整数值进行排序，然后选择整数值较低的国家。

但似乎我这样做的时间很长，而且它不是很随机。你对如何有效地解决这个问题有什么建议吗？

4

2 回答 2

3

这里与遗传算法中使用的称为轮盘赌选择的技术有相似之处。

实现起来非常简单：

  1. 创建一个国家数组，其大小是所有国家的整数总和
  2. 将每个国家 N 次放入数组中，其中 N 是城市的数量
  3. 随机选择数组中的一个值

这些国家将以其城市数量的概率被选中

编辑：如果城市数量非常多，您可以通过除以最低城市数量来标准化数字，以便每个国家/地区都保留在表格中。

于 2013-11-04T16:37:36.680 回答
0

我想选择一组城市数量最少的国家。

然后你想要一个List国家的顺序或城市数量。为什么不创建一个Country包含List城市的类

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();
   }
}

现在您可以像这样根据城市数量对国家列表进行排序

... // 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;
        }
    });

我刚刚使用以下方法对此进行了测试（注意：我向 Country 添加了一个“toString()”方法）

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());
    }

}

和输出

 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
于 2013-11-04T16:32:29.520 回答