Pair elements of two lists by condition without reusing elements

Question

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)

Answer 1

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.

Answer 2

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

Answer 3

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[0] and len(groups[0]) != len(groups[1]):
            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.