Finding tuples with a common element

问题:

Suppose I have a set of tuples with people's names. I want to find everyone who shares the same last name, excluding people who don't share their last name with anyone else:

# input
names = set([('John', 'Lee'), ('Mary', 'Miller'), ('Paul', 'Ryan'), 
             ('Bob', 'Ryan'), ('Tina', 'Lee'), ('Bob', 'Smith')])

# expected output
{'Lee': ['Tina', 'John'], 'Ryan': ['Bob', 'Paul']} # or similar

This is what I am using

def find_family(names):
    result = {}

    try:
        while True:
            name = names.pop()
            if name[1] in result:
                result[name[1]].append(name[0])
            else:
                result[name[1]] = [name[0]]
    except KeyError:
        pass

    return dict(filter(lambda x: len(x[1]) > 1, result.items()))

This looks ugly and inefficient. Is there a better way?

回答1:

defaultdict can be used to simplify the code:

from collections import defaultdict

def find_family(names):
    d = defaultdict(list)
    for fn, ln in names:
        d[ln].append(fn)
    return dict((k,v) for (k,v) in d.items() if len(v)>1)

names = set([('John', 'Lee'), ('Mary', 'Miller'), ('Paul', 'Ryan'), 
             ('Bob', 'Ryan'), ('Tina', 'Lee'), ('Bob', 'Smith')])
print find_family(names)

This prints:

{'Lee': ['Tina', 'John'], 'Ryan': ['Bob', 'Paul']}

回答2:

Instead of using a while loop, use a for loop (or similar construct) over the set contents (and while you're at it, you can destructure the tuples):

for firstname, surname in names:
    # do your stuff

You might want to use a defaultdict or OrderedDict (http://docs.python.org/library/collections.html) to hold your data in the body of the loop.

回答3:

>>> names = set([('John', 'Lee'), ('Mary', 'Miller'), ('Paul', 'Ryan'), 
...              ('Bob', 'Ryan'), ('Tina', 'Lee'), ('Bob', 'Smith')])

You can get a dictionary of all the people where the keys are their lastnames easily with a for-loop:

>>> families = {}
>>> for name, lastname in names:
...   families[lastname] = families.get(lastname, []) + [name]
... 
>>> families
{'Miller': ['Mary'], 'Smith': ['Bob'], 'Lee': ['Tina', 'John'], 'Ryan': ['Bob', 'Paul']}

Then, you just need to filter the dictionary with the condition len(names) > 1. This filtering could be done using a "dictionary comprehension":

>>> filtered_families = {lastname: names for lastname, names in families.items() if len(names) > 1}
>>> filtered_families
{'Lee': ['Tina', 'John'], 'Ryan': ['Bob', 'Paul']}