algorithm - 组合益智游戏

Question

我想知道解决以下问题的最佳方法是什么:

我现在有一个Map<String, Collection<String>> .假设它是一张膳食 map ，其中包含您可以在该膳食中提供的一系列饮料。例如

早餐 - 橙汁 早餐 - 咖啡

午餐 - 橙汁 午餐 - 汽水 午餐 - 啤酒

晚餐 - 汽水 晚餐 - 啤酒 晚餐 - Wine

所以我的收藏真的是Map<Meal, Collection<Beverage>>

我需要做的是创建一个 List<Map<String,String>>用餐时的所有各种饮料组合。在这种情况下，我将有 18 种组合。例如

[

[ 早餐 -> 橙汁， 午餐 -> 橙汁， 晚餐 -> 汽水 ]

[ 早餐 -> 橙汁， 午餐 -> 橙汁， 晚餐 -> 啤酒 ]

[ 早餐 -> 橙汁， 午餐 -> 橙汁， 晚餐 -> Wine ]

[ 早餐 -> 橙汁， 午餐 -> 苏打水， 晚餐 -> 苏打水， ]

等等... ]

我很想知道其他人会如何着手创建最终系列。

另外，我使用的是 java，所以漂亮的功能性东西是禁止使用的。

谢谢

编辑

膳食类型是动态的。也就是说，可以从列表中删除晚餐或添加早午餐。

Answer 1

如果我做对了，这里没有魔法，只需在嵌套循环中迭代 3 个集合。

for (String breakfastBev : breakfast) {
  for (String lunchBev : lunch) {
    for (String dinnerBev : dinner) {
      System.out.println(breakfastBev + ", " + lunchBev + ", " + dinnerBev);
    }
  }
}

我相信现在您可以弄清楚如何使用您的 Map 和输出 List 来完成它。 :-)

编辑:对于更改后的需求，一种方法是递归:

main() {
    List<Map<String, String>> output = new ArrayList<Map<String, String>>();
    recordBeverages(new HashMap(), beveragesByMeal, output);
}

void recordBeverages(Map visited, Map meals, List<Map> output) {
    if(meals.isEmpty()) {
        output.add(visited);
    }
    String mealType = meals.keySet().iterator().next();
    Map remainingMeals = new HashMap(visited);
    remainingMeals.keySet().remove(mealType);
    for(Beverage bev : meals.get(mealType)) {
        Map newVisited = new HashMap(visited);
        newVisited.put(mealType, bev);    

        recordBeverages(newVisited, remainingMeals, output);
    }
}

未经测试，但您明白这一点。