获得最大对，而不重复dictricion密钥(Get maximum pairs without repetition of dictrionary key)

我正努力获得我的列表的最大利用率（ “削减” ）。

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

这是我得到的地方：

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对 。我在这里错过了一招吗？

UPDATE

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

我不关心巴黎，只要k2不匹配，我已经获得了最有效率的对列表，即在我上面的代码中，我浪费了 1个可能的对，不使用字典与k2：d因此这不是最有效的组合。

如果仍然不清楚，我会道歉，也许我说错了。

I’m struggling with getting maximum utilisation ("paring") of my list.

I have a list of dictionaries where I would like to get maximum number of "pares" as long as a given k2 is not matching. I guess some sort of permutation whitch shrinking resource list?

This is where I got:

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

The problem is that I’m left with t2 = [{'k2': 'd', 'k1': 6}, {'k2': 'd', 'k1': 8}]

Which is a waste of 1 pair. Manually I can achieve something like:

({'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})

or similar with total of 4 pairs. am I missing a trick here?

UPDATE

What I need is that every time a pair is created I need to remove the items from the list, thus I can get only 4 paris doing this manually.

I don't "care" about the paris as long as k2 doesn't match and I have obtained the most efficinet list of pairs i.e. in my code above I wasted 1 possible pair by not using dictionary with k2: d thus this was not the most efficient combination.

I do appologise if this is still not clear, perhaps I'm presenting it wrong.

最满意答案

为了获得最大数量的可能对，您必须以智能方式创建对。考虑这样的输入：

k2_values = ['a', 'c', 'b', 'b']

如果你不打算正确地构建对，你最终可能会配对a和c ，这会阻止你创建第二对，因为你只剩下2 b了。要获得最大数量的对，您必须开始使用您最常用的值构建对 - 使用b 。

因此，第一步是按照k2值对您的dicts列表进行分组：

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

然后按长度对这些组进行排序：

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

最后从这些组中构建对。

履行

import operator import collections def make_pairs(dicts, keyfunc): if isinstance(keyfunc, str): keyfunc = operator.itemgetter(keyfunc) # group the dicts by k2 values grouped_dicts = collections.defaultdict(list) for dic in dicts: key = keyfunc(dic) grouped_dicts[key].append(dic) # sort the groups by size grouped_dicts = sorted(grouped_dicts.values(), key=len, reverse=True) # iterate over the groups and build pairs iters = [(len(group), iter(group)) for group in grouped_dicts] iters_itr = iter(iters) len1, itr1 = next(iters_itr) for len2, itr2 in iters_itr: # make sure the shorter iterator comes first if len1 > len2: itr1, itr2 = itr2, itr1 len1, len2 = len2, len1 yield from zip(itr1, itr2) # discard the exhausted iterator and re-calculate # the remaining length itr1 = itr2 len1 = len2 - len1

测试运行：

>>> list(make_pairs(t, 'k2')) [({'k1': 3, 'k2': 'b'}, {'k1': 1, 'k2': 'a'}), ({'k1': 4, 'k2': 'b'}, {'k1': 2, 'k2': 'a'}), ({'k1': 7, 'k2': 'a'}, {'k1': 6, 'k2': 'd'}), ({'k1': 8, 'k2': 'd'}, {'k1': 5, 'k2': 'c'})]

In order to get the maximum number of possible pairs, you have to create the pairs in a smart way. Consider an input like this:

k2_values = ['a', 'c', 'b', 'b']

If you don't care to build the pairs correctly, you might end up pairing a and c, which would prevent you from creating a 2nd pair because you only have 2 bs left. To get the maximum number of pairs, you have to start building pairs with those values that you have the most of - with b.

Thus, the first step is to group your list of dicts by the k2 value:

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

Then sort those groups by length:

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

And finally build pairs from these groups.

Implementation

import operator import collections def make_pairs(dicts, keyfunc): if isinstance(keyfunc, str): keyfunc = operator.itemgetter(keyfunc) # group the dicts by k2 values grouped_dicts = collections.defaultdict(list) for dic in dicts: key = keyfunc(dic) grouped_dicts[key].append(dic) # sort the groups by size grouped_dicts = sorted(grouped_dicts.values(), key=len, reverse=True) # iterate over the groups and build pairs iters = [(len(group), iter(group)) for group in grouped_dicts] iters_itr = iter(iters) len1, itr1 = next(iters_itr) for len2, itr2 in iters_itr: # make sure the shorter iterator comes first if len1 > len2: itr1, itr2 = itr2, itr1 len1, len2 = len2, len1 yield from zip(itr1, itr2) # discard the exhausted iterator and re-calculate # the remaining length itr1 = itr2 len1 = len2 - len1

Test run:

>>> list(make_pairs(t, 'k2')) [({'k1': 3, 'k2': 'b'}, {'k1': 1, 'k2': 'a'}), ({'k1': 4, 'k2': 'b'}, {'k1': 2, 'k2': 'a'}), ({'k1': 7, 'k2': 'a'}, {'k1': 6, 'k2': 'd'}), ({'k1': 8, 'k2': 'd'}, {'k1': 5, 'k2': 'c'})]

更多推荐