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
        if not found:
            raise Exception("Not found: %s" % a)

result = list(match(list1, list2, key=keyfunc)
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]

    g.add_nodes_from(l, bipartite=0)
    g.add_nodes_from(r, bipartite=1)

    edges = [(a,b) for a in l for b in r if a[2] == b[2]]
    g.add_edges_from(edges)

    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[1], n[2]) 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