如何用递归算法枚举水果分配给人员的所有可行方案

你的思路完全可行，只是漏掉了「当总人数多于水果数时，当前的人可以选择不分配水果（即分配nil）」的分支，补充后就能覆盖两种示例场景。

核心规则梳理 #

• 每个水果最多分给1个人，不可重复分配
• 最终分配的非nil水果总数为 k = min(总人数, 总水果数)：人多的时候全部分完水果、剩下的人拿nil；水果多的时候给所有人都分配不同的水果、剩余水果不用处理

递归逻辑设计 #

1. 基准终止条件
   • 待分配人员为空时，返回仅包含空分配方案的数组 [{}]
   • 剩余需要分配的水果数为0时，剩下的所有人员统一分配nil
   • 剩余待分配人数等于剩余需要分配的水果数时，剩下的所有人必须分配水果，不能选nil
2. 递归步骤
   取出当前待分配的第一个人，分两个分支处理：
   • 分支1（分配水果）：如果还有需要分配的水果，遍历当前所有可用水果，将当前水果分配给第一个人，再递归计算剩余人员分配剩余水果的所有子方案，将当前分配关系合并到所有子方案中
   • 分支2（分配nil）：如果剩余人数多于剩余需要分配的水果数，给当前人分配nil，再递归计算剩余人员分配全部当前可用水果的所有子方案，将当前分配关系合并到所有子方案中
3. 合并两个分支的所有方案，就是当前层级的全部可行解

代码实现（Ruby，匹配示例语法） #

def all_fruit_assignments(people, fruits)
  k = [people.size, fruits.size].min
  recursive_assign(people, fruits, k)
end

def recursive_assign(remaining_people, remaining_fruits, need_assign_count)
  # 终止条件1：没有待分配的人，返回空方案
  return [{}] if remaining_people.empty?
  # 终止条件2：不需要再分配水果，剩下的人全部分nil
  if need_assign_count == 0
    nil_assign = remaining_people.to_h { |p| [p, nil] }
    return [nil_assign]
  end
  # 终止条件3：剩余人数刚好等于需要分配的水果数，所有人必须分配水果，不能选nil
  if remaining_people.size == need_assign_count
    current_p = remaining_people.first
    rest_p = remaining_people[1..]
    solutions = []
    remaining_fruits.each do |f|
      rest_f = remaining_fruits - [f]
      sub_solutions = recursive_assign(rest_p, rest_f, need_assign_count - 1)
      sub_solutions.each { |sub| solutions << sub.merge({ current_p => f }) }
    end
    return solutions
  end

  current_p = remaining_people.first
  rest_p = remaining_people[1..]
  total_solutions = []

  # 分支1：给当前人分配一个可用水果
  remaining_fruits.each do |f|
    rest_f = remaining_fruits - [f]
    sub_solutions = recursive_assign(rest_p, rest_f, need_assign_count - 1)
    sub_solutions.each { |sub| total_solutions << sub.merge({ current_p => f }) }
  end

  # 分支2：给当前人分配nil
  sub_solutions_nil = recursive_assign(rest_p, remaining_fruits, need_assign_count)
  sub_solutions_nil.each { |sub| total_solutions << sub.merge({ current_p => nil }) }

  total_solutions
end

测试验证 #

示例1测试 #

people1 = ["Terry", "Merry"]
fruits1 = ["Apple","Grape","Peach"]
result1 = all_fruit_assignments(people1, fruits1)
puts result1.inspect
# 输出和示例1完全一致，共6个方案，无nil

示例2测试 #

people2 = ["Terry", "Merry", "Perry"]
fruits2 = ["Apple","Grape"]
result2 = all_fruit_assignments(people2, fruits2)
puts result2.inspect
# 输出和示例2完全一致，共6个方案，每个方案有1个nil

内容的提问来源于stack exchange，提问作者james