Java 递归食物分配

Question

我有以下列表:

动物食品鲶鱼狗 pig 肉 牛肉我想以尽可能多的不同方式为动物分配食物，例如:

每种不同的动物和食物组合都将存储在 map 中。

(猫吃鱼，狗吃 pig 肉)

(猫吃鱼，狗吃牛肉)

(猫吃 pig 肉，狗吃鱼)

(猫吃 pig 肉，狗吃牛肉)

(猫吃牛肉，狗吃鱼)

(猫吃牛肉，狗吃 pig 肉)

最后所有的 map 都会被放入一个集合中并返回。

我正在尝试使用递归函数来实现相同的目的，以下是我的尝试方法..但我无法正确执行它，所以请帮助我完成它。

提前致谢!!!

private static Set<Map<Animal, Food>> eats(List<Animal> animal, List<Food> food) {
    Set<Map<Animal, Food>> returnSet = new HashSet<Map<Animal, Food>>();
    Map<Animal, Food> map = new HashMap<Animal, Food>();
    if (animal.size() == 0) {
        return null; // There is no animal to feed
    } else {
        animalLoop: for (int i = 0; i < animal.size(); i++) {
            foodLoop: for (int j = 0; j < food.size(); j++) {
                map.put(animal.get(i), food.get(j));
                food.remove(j);
                break venueLoop;
                }
            }
            animal.remove(i);
            returnSet.add(map);
        }

    }
    return returnSet.add(eats(animal, food));
}

Answer 1

如果我们需要保留方法指纹并且不运行全局访问跟踪结构，这里有一个可供引用的工作程序。

import java.util.*;
import java.util.stream.Collectors;

public class SFO_Recursive {
    public enum Animal {
        CAT, DOG ;
    }
    public enum Food {
        FISH, BEEF, PORK ;
    }

    private static Set<Map<Animal, Food>> eats(List<Animal> animal, List<Food> food) {
        Set<Map<Animal,Food>> fleet = new HashSet();
        for (Animal a: animal){
            for (Food f: food){
                // Take a step with (a, f)
                List<Food> food_left = food.stream().filter(x -> !x.equals(f)).collect(Collectors.toList());
                List<Animal> animal_left = animal.stream().filter(x -> !x.equals(a)).collect(Collectors.toList());
                if (animal_left.isEmpty() || food_left.isEmpty()){
                    // Terminal state
                    fleet.add(new HashMap<Animal, Food>(){{put(a,f);}});
                }else {
                    eats(animal_left, food_left).stream().forEach(s -> {s.put(a, f); fleet.add(s); });
                }
            }
        }
        return fleet;
    }

    public static void main(String[] args){
        SFO_Recursive.eats(
            Arrays.asList(Animal.CAT, Animal.DOG),
            Arrays.asList(Food.BEEF, Food.FISH, Food.PORK)
        ).stream().forEach(System.out::println);
    }
}

结果是:

{CAT=BEEF, DOG=PORK}
{CAT=PORK, DOG=BEEF}
{CAT=BEEF, DOG=FISH}
{CAT=FISH, DOG=BEEF}
{CAT=FISH, DOG=PORK}
{CAT=PORK, DOG=FISH}

对于递归深度优先搜索，有两件事需要注意:最终状态条件，以及如何将当前步骤应用于( future )最终状态的部分结果。

如果我们必须保留方法指纹以返回带有两个列表输入的 Set。终止条件是任一参数中明显的空列表以停止搜索。要将当前步骤应用于 Set，我们可以循环所有 Map，只需将新的 Animal obj 和新的 Food obj 的组合添加到每个 Map，但依靠 Set 类来检查是否添加了唯一的 Map。如果没有全局跟踪表，我们可以从动物和食物列表中删除消耗的元素，以将信息发送到下一个状态。

Java 通过 hashCode() 来测试相等性。 Map 将 hashCode 计算为所有条目的总和，每个条目采用 hashCode(k) ^ hashCode(v)。默认情况下，每个枚举值都有一个唯一的 hashCode。因此，直接添加Map元素是可以的。