python - 获取最大对而不重复字典键

Question

我正在努力最大限度地利用我的列表(“配对”)。

我有一个字典列表，只要给定的k2不匹配，我就希望获得最大数量的“pares”。我猜想某种排列会缩小资源列表？

这是我得到的:

t = [ {'k1': 1, 'k2': 'a'},
      {'k1': 2, 'k2': 'a'},
      {'k1': 3, 'k2': 'b'},
      {'k1': 4, 'k2': 'b'},
      {'k1': 5, 'k2': 'c'},
      {'k1': 6, 'k2': 'd'},
      {'k1': 7, 'k2': 'a'},
      {'k1': 8, 'k2': 'd'}]

t2 = t[:]

for d in t2:
    for x in t2:
        if d['k2'] != x['k2']:
            print(d,x)
            t2.remove(x)
            t2.remove(d)
            break

问题是我只剩下 t2 = [{'k2': 'd', 'k1': 6}, {'k2': 'd', 'k1': 8}]

这浪费了1对。手动我可以实现以下目标:

({'k2': 'a', 'k1': 1}, {'k2': 'b', 'k1': 3})
({'k2': 'b', 'k1': 4}, {'k2': 'a', 'k1': 2})
({'k2': 'd', 'k1': 6}, {'k2': 'c', 'k1': 5})
({'k2': 'a', 'k1': 7}, {'k2': 'd', 'k1': 8})

或类似的总共 4 对。我在这里错过了一个技巧吗？

更新

我需要的是，每次创建一对时，我都需要从列表中删除项目，因此我只能让 4 个巴黎人手动执行此操作。

只要 k2 不匹配，我就不会“关心”巴黎，并且我已经获得了最有效对列表，即在上面的代码中我浪费了 k2: d 的字典，可以得到 1 个可能的对，因此这不是最有效的组合。

如果这仍然不清楚，我深表歉意，也许我表述错误。

Answer 1

虽然我不完全确定，但这有 bin packing problem 的感觉。 。您的垃圾箱可容纳 2 件根据某种定义具有独特值(value)的元素。问题陈述是尽量减少已用垃圾箱的数量，或者换句话说，如果可能的话，避免生产仅包含 1 件元素的垃圾箱。

实现 first-fit近似解相当简单。它不会为所有值产生完美的结果，但碰巧它确实找到了适合您的最佳解决方案:

def pairs(t, key):
    bins = []
    full = []

    for d in t:
        for i, (k, p) in enumerate(bins):
            if d[key] != k:
                p.append(d)
                full.append(p)
                # This is okay only because we do not continue
                # iterating after mutation.
                del bins[i]
                break

        else:
            # No bin could hold this d, so create a new one
            bins.append((d[key], [d]))

    return full

作为附加措施，您可以首先按频率对值进行排序，使其成为一种首次拟合降序:

def pairs(t, key):
    lookup = defaultdict(list)

    for d in t:
        lookup[d[key]].append(d)

    gs = sorted(lookup.values(), key=len, reverse=True)
    ds = [d for g in gs for d in g]

    bins = []
    full = []

    for d in ds:
        ...

    ...