# Pair elements of two lists by condition without reusing elements

I have two lists that I want to join on a condition. Unlike in a relational algebra join, if more than one element of each list can be matched, only one should be selected, and shouldn't then be reused. Also, if any of the elements of the first list don't match any of the second list, the process should fail.

Example:

# inputs
list1 = [{'amount': 124, 'name': 'john'},
{'amount': 456, 'name': 'jack'},
{'amount': 456, 'name': 'jill'},
{'amount': 666, 'name': 'manuel'}]
list2 = [{'amount': 124, 'color': 'red'},
{'amount': 456, 'color': 'yellow'},
{'amount': 456, 'color': 'on fire'},
{'amount': 666, 'color': 'purple'}]
keyfunc = lambda e: e['amount']

# expected result
[({'amount': 124, 'name': 'john'}, {'amount': 124, 'color': 'red'}),
({'amount': 456, 'name': 'jack'}, {'amount': 456, 'color': 'yellow'}),
({'amount': 456, 'name': 'jill'}, {'amount': 456, 'color': 'on fire'}),
({'amount': 666, 'name': 'manuel'}, {'amount': 666, 'color': 'purple'})]


I've written a working implementation in Python, but it seems clunky, unclear and inefficient:

def match(al, bl, key):
bl = list(bl)
for a in al:
found = False
for i, b in enumerate(bl):
if key(a) == key(b):
found = True
yield (a, b)
del bl[i]
break

result = list(match(list1, list2, key=keyfunc)

• Is there a specific reason to keep the dictionaries separated? I mean, could the return value be like [{'amount': 124, 'name': 'john', 'color': 'red'}, {'amount': 456, 'name': 'jack', 'color': 'yellow'}, …]? Feb 13, 2018 at 10:05
• @MathiasEttinger I wanted to keep the match() function generic; the entries may not necessarily be dictionaries, or the caller may want to merge them differently (e.g. only copying a subset of the keys from one to the other). Feb 13, 2018 at 10:18
• Is list2 allowed to have unused elements? Feb 13, 2018 at 21:59
• @EricDuminil yes Feb 14, 2018 at 9:46

I think you could simplify your code a bit by considering the second list to be a dictionary mapping the key to list of values with the same key. This would avoid doing a linear search over the second list for each element of the first list, and also lends itself to less code:

from collections import defaultdict

def match(al, bl, key):
table = defaultdict(list)
for b in bl:
table[key(b)].append(b)
return [(a, table[key(a)].pop(0)) for a in al]


The function will raise an IndexError exception in case the key does not reference a matching element in bl.

• What's slightly "meh" with this proposal in my opinion is that the list comprehension relies on a side effect of pop, namely that it removes the selected element from the list. Feb 13, 2018 at 20:12
• That's nice and concise. I'd say that pop's main job is to remove an element, it really isn't surprising at all IMHO. Your method doesn't detect if b has unused elements. I'm not sure if that's a bug or a feature. I'll ask OP. Feb 13, 2018 at 21:58
• @EricDuminil To me, a list comprehension is a declarative construct (as opposed to an imperative for loop) much like in Haskell (from which Python derived list comprehensions). In this mathematical sense, the value to which each element in the input sequence is mapped does not depend on other values (resp. the order in which they are processed). This independence among the elements is broken by the pop call (due to which you depend on a very specific order in which the list comprehension processes the elements in al). Feb 14, 2018 at 7:28
• @EricDuminil As for detecting unused elements in bl, this could be tested after the list comprehension by checking if any(not x for x in table.values()) holds. Feb 14, 2018 at 7:33
• No need to, according to OP, your behaviour is a feature and not a bug ;) Well done! Feb 14, 2018 at 9:53

# Theory

It might not be clear at first, but you're basically describing a bipartite graph. You're interested in finding the maximum matching and if it's perfect.

NetworkX is a great Python library for graphs, and the maximum_matching function is already implemented. It uses the Hopcroft-Karp algorithm and runs in $$\O(n^{2.5})\$$ where $$\n\$$ is the number of nodes.

You only have to preprocess your lists into a graph and let networkx do its job.

# Code

Here's a slightly modified version of a previous answer on Stack Overflow:

import networkx as nx
import matplotlib.pyplot as plt

def has_a_perfect_match(list1, list2):
if len(list1) != len(list2):
return False

g = nx.Graph()

l = [('l', d['name'],  d['amount']) for d in list1]
r = [('r', d['color'], d['amount']) for d in list2]

edges = [(a,b) for a in l for b in r if a == b]

pos = {}
pos.update((node, (1, index)) for index, node in enumerate(l))
pos.update((node, (2, index)) for index, node in enumerate(r))

m = nx.bipartite.maximum_matching(g, l)
colors = ['blue' if m.get(a) == b else 'gray' for a,b in edges]

nx.draw_networkx(g,
pos=pos,
arrows=False,
labels = {n:"%s\n%d" % (n, n) for n in g.nodes()},
edge_color=colors)
plt.axis('off')
plt.show()

return len(m) // 2 == len(list1)


As a bonus, it displays a diagram with the graph and maximum matching:

list1 = [{'amount': 124, 'name': 'john'},
{'amount': 456, 'name': 'jack'},
{'amount': 456, 'name': 'jill'},
{'amount': 666, 'name': 'manuel'}]
list2 = [{'amount': 124, 'color': 'red'},
{'amount': 456, 'color': 'yellow'},
{'amount': 456, 'color': 'on fire'},
{'amount': 666, 'color': 'purple'}]

print(has_a_perfect_match(list1, list2))
# True list1 = [{'amount': 124, 'name': 'john'},
{'amount': 456, 'name': 'jack'},
{'amount': 457, 'name': 'jill'},
{'amount': 666, 'name': 'manuel'}]
list2 = [{'amount': 124, 'color': 'red'},
{'amount': 458, 'color': 'yellow'},
{'amount': 456, 'color': 'on fire'},
{'amount': 666, 'color': 'purple'}]

print(has_a_perfect_match(list1, list2))
# False # Notes

The desired matching is in m and has a slightly different format than what you mentioned:

{('l', 'jack', 456): ('r', 'yellow', 456), ('l', 'jill', 456): ('r', 'on fire', 456), ('l', 'john', 124): ('r', 'red', 124), ('l', 'manuel', 666): ('r', 'purple', 666), ('r', 'red', 124): ('l', 'john', 124), ('r', 'yellow', 456): ('l', 'jack', 456), ('r', 'purple', 666): ('l', 'manuel', 666), ('r', 'on fire', 456): ('l', 'jill', 456)}


It does have enough information, though.

Note that the edge generation isn't optimal (it's $$\O(n^{2})\$$ and could be $$\O(n)\$$ with dicts) but it's concise and still faster than the matching algorithm. Feel free to modify it!

# Optimization

@Peilonrayz' answer has a better performance because your problem is easier than the general matching problem : there are no connections between nodes with distinct ids, so a greedy algorithm works fine.

Actually, it's possible to check in 2 lines if the lists match. With a Counter, you just need to check if the distribution (e.g. Counter({124: 1, 456: 2, 666: 1})) is the same for both lists:

from collections import Counter
Counter(map(key, list1)) == Counter(map(key, list2))
# True

• Thanks! While my case is in fact simple and easier, I appreciate knowing the theory of the problem; it'll help me more when I come across similar problems in the future. Feb 13, 2018 at 15:36

I think you should split your code into two functions.

1. You should add some code to group your object lists together. I'd call this group_by.
2. Take the first from each match, and error in the match function.

To perform the first function, I'd use collections.defaultdict, so that you only generate the keys that you need. This also has the benefit of having $O(kn)$ performance, rather than $O(n^k)$. Where $n$ is the amount of objects in each list, and $k$ are the amount of lists.

After this you can check if there are enough items to yield correctly. This is two checks, 1 that there are items in the first group. Then you check that there are the same amount of items in both groups. After this, you can use zip to group together items in pairs.

import collections

def group_by(lists, key):
amount = range(len(lists))
d = collections.defaultdict(lambda:tuple([[] for _ in amount]))
for i, objects in enumerate(lists):
for obj in objects:
d[key(obj)][i].append(obj)
return d

def match(al, bl, key):
for key, groups in group_by((al, bl), key).items():
if groups and len(groups) != len(groups):
raise ValueError("Missing value for {!r}".format(key))
yield from zip(*groups)


The type of exception that should be raised is debatable, however it shouldn't be Exception.

• If you think the error is predominantly due to missing values, then using ValueError would probably be best.
• If you think the error is because it requires there to be a common key, then KeyError or LookupError may be better.
• Alternately if you're planning on making an entire rational algebra Python library, create your own exceptions.
• Darn it, too fast, I was thinking about something alike. I wonder, though, how missing entries are handled when considering PEP 479 and adding a from __future__ import generator_stop? Feb 13, 2018 at 10:30
• I don't want to take only the first item from each group; I just don't want to reuse items in different matches. I can understand the group_by, but I don't see how match here accomplishes the expected result. Feb 13, 2018 at 10:40
• @MathiasEttinger That's a good question, there was a bug I failed to notice without that enabled. Generators stop when they encounter StopIteration, I thought it passed through. With the future it fails on the iter rather than the raise now. Thanks, :) Feb 13, 2018 at 10:41
• @Peilonrayz only one for each match, not in total. Please look at the expected result in the example. Feel free to suggest any improvements on the text of the question as well :) Feb 13, 2018 at 10:43
• @Peilonrayz Yes, that's what I thought. I took advantage of this behaviour in the past… Now I feel a bit sad, somehow, as you won't be able to rely on a generator to "swallow" a StopIteration. Feb 13, 2018 at 10:44