从集合列表选元素组合以获取最多唯一数的高效解法

假设有一个集合数组，每个集合包含任意数量的整数：

A = {1,2,3}
B = {1,3,4,5,6}
C = {4,5,6,10}
SETS = [A, B, C]

每个集合对应一个小于其元素数量的数值，我们称之为**选择数（selection number）**或Set_x：

A_x = 1
B_x = 4
C_x = 3
SELECTION_NUMS = [A_x, B_x, C_x]

我需要从每个集合中选择Set_x个元素的任意组合（例如从集合A选1个元素，从集合B选4个元素等），使得选中的所有元素中唯一数的数量最多。如何以最高效的方式实现这一点？

示例对比：

• 若从A中选{1}，从B中选{1,3,4,5}，从C中选{4,5,6}，选中的总唯一元素为{1,3,4,5,6}，共5个。
• 但从A中选{2}，从B中选{1,3,4,5}，从C中选{4,6,10}，总唯一元素为{1,2,3,4,5,6,10}，共7个。这是暴力法计算得出的最优解。

扩展场景 #

每个整数新增一个stars属性，取值范围为1-5星（例如1值5星，2值3星）。此时Set_x变为可选中元素的总stars数阈值，比如可以从集合D中选{1,2}，因为总stars数5+3=8等于D_x。

暴力解法代码 #

import itertools
def brute_force(SETS, SELECTION_NUMS):
  NUM_SETS = len(SETS)
  all_perms = list()
  for i in range(NUM_SETS):
    all_perms_per_set = list()
    for perm in itertools.permutations(SETS[i], r=SELECTION_NUMS[i]):
      perm = set(perm)
      all_perms_per_set.append(perm)
    all_perms.append(all_perms_per_set)

  MAX_NUM_ELEMENTS = sum(SELECTION_NUMS)
  most_num_elements = 0
  most_combined_set = set()
  for combination in itertools.product(*all_perms):
    combined_set = set().union(*combination)
    if len(combined_set) > most_num_elements:
      most_num_elements = len(combined_set)
      most_combined_set = combined_set
    if len(combined_set) == MAX_NUM_ELEMENTS:  # 所有选中元素均唯一
      break

  return most_num_elements, most_combined_set

当前思路困境 #

• 统计每个数字的出现次数，例如：count = {1: 2, 2: 1, 3: 2, 4: 2, 5: 2, 6: 2, 7: 0, 8: 0, 9: 0, 10: 1}，然后优先选择出现次数最少的元素，重复此过程。但不确定这种方法是否完全可靠，比如当出现次数最少的数字存在于多个集合中时，该依据什么标准选择从哪个集合中选中它？
• 逐个修改集合的选择内容：先为每个集合选择唯一元素，直到出现冲突选择，此时修改其中一个冲突集合的选择。不确定这种迭代方法能否覆盖所有组合并找到最优组合；此外，由于无法确定可选中的理论最大唯一元素数，难度进一步加大。

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