这是一道排序算法题。我分成一个大纲，这样阅读起来会更快。
故事。想象一个八胞胎家庭——全是女孩。每天早上，妈妈都要给这八个女孩穿上衬衫和裤子(如果你愿意，也可以穿 Boot 和裤子)。妈妈总是买配套的衣服——有时是几双——但并不是所有的衣服在任何时候都是干净的。
设置。每天早上，妈妈都会从两个垃圾箱开始:干净的衬衫和干净的裤子。
目标。自动为每件衬衫搭配一条“风格匹配”的裤子(妈妈不想考虑什么匹配--it's a thing)。
重要。输入集有重复项(这与按唯一键 排序不同)。我们假设衬衫和裤子被分为几类(标识一种“风格”)。我们将每个类命名为:
s1, s2, s3, ..., sn。裤子也一样:p1, p2, p3, ..., pn。每个s1都与一个p1匹配。匹配对可以记为:(s1, p1)。输入。 因此，干净衬衫的箱子可以描述为:
shirts = [s1,s2,s2,s3,s4,s4,s4,s5,s6,s7,s8]裤子也一样:
pants = [p1,p2,p2,p3,p4,p4,p5,p6,p8,p11,13]问题。妈妈有足够的衣服让女孩们穿去上学吗？如果妈妈随机挑选任何一条
[s6,s7]，她将找不到匹配的裤子，因为剩余的干净裤子[p11,p13]将不匹配。戏剧!实际上，计数是一个简单的问题。难题。妈妈总是想知道她是否需要洗衣服。 AND，哪些衬衫或裤子不再匹配。因此，该算法的扩展是返回匹配和不匹配的报告。
matches = [(s1,p1), (s2,p2), (s2,p2), (s3,p3), (s4,p4), (s4,p4) (s5,p5) (s6,p6), {s8,p8)] mismatches = [(s4,s7), (p11,p13)]
我的第一次尝试。我正在使用 Python。我认为这将是一个简单的问题。我会做一个嵌套的 for() 循环:
for s in shirts:
for p in pants:
if s matches p:
give to kid #1
else:
continue
行不通。我不能不考虑一条相配的裤子。
具体来说，shirts 有子集 [s4,s4,s4] 而 pants 有子集 [p4,p4] 。每次，这个嵌套的 for() 循环都会选取下一个 s4，它只会匹配第一个 p4——算法不会知道只有两条 p4 裤子!
我的下一个想法，对衬衫/裤子垃圾箱进行分类。将重复项拆分到新的箱子中，像使用递归算法一样重复。
或者，因为我使用的是 Python，我是否应该计算重复项并根据项目的 max 计数制作 n 空列表穿着衬衫和裤子。有两个输入集，如果第一组有 3 个倍数而第二组有 6 个倍数，这似乎会变得复杂——现在我需要确定哪个输入的重复次数最多。
或者。如果已经存在有效的递归解决方案，则强制 Python 使用非 Pythonic 的东西。
最佳答案
听起来你需要一个多套 - 在 python 中这是 collections.Counter，如果你将衬衫和裤子映射到它们匹配的装备:
>>> shirts = [1,2,2,3,4,4,4,5,6,7,8]
>>> pants = [1,2,2,3,4,4,5,6,8,11,13]
>>> s = Counter(shirts)
>>> p = Counter(pants)
>>> s & p # matched outfits
Counter({1: 1, 2: 2, 3: 1, 4: 2, 5: 1, 6: 1, 8: 1})
这显示了所有完整的服装，即 9 套完整的服装。
您还可以找出哪些衬衫和裤子不匹配:
>>> s - p # mismatch shirts
Counter({4: 1, 7: 1})
>>> p - s # mismatch pants
Counter({11: 1, 13: 1})
关于python - 什么算法解决方案可以匹配包含倍数的两个垃圾箱之间的项目？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44092067/