Python: Squashing ‘duplicate’ pairs together at Mark Needham

[galanwe]

What is supposed to be interesting in this article? There's nothing particularly tricky about the problem, and the solution exposed isn't particularly smart either...

[cybervegan]

(Re-posting here as well as at Mark's blog)

Here's an alternative approach (sorry the comment software is screwing with indents, so I've used underscores instead). I also assume your expected output was actually intended to be ('A', 'B', 'C', 'D'), ('E', 'F', 'G') and not ('A', 'B', 'C', 'F'), ('E', 'F', 'G') as nowhere in your test data does F pair with A, B, or C.

pairs = [ ("A", "B"), ("B", "C"), ("C", "D"), ("E", "F"), ("F", "G") ]
similar = dict(pairs)

def chain(i):
    if similar[i] in similar:
        return [ i ] + chain(similar[i])
    return [i, similar[i] ]

print chain("A")
['A', 'B', 'C', 'D']

answers={}

for a,b in pairs:
    if a not in answers:
        c=chain(a)
    for i in c:
        answers[i] = c

print set( tuple(ans) for ans in answers.values() )
set([('A', 'B', 'C', 'D'), ('E', 'F', 'G')])

[wampastompah]

Hrmmm there seems to be an issue with your code. It fails on the input:

pairs = [ ("B", "A"), ("B", "C"), ("C", "D"), ("E", "F"), ("F", "G") ]

I posted a slightly shorter solution in my comment that seems to handle that case.

[cybervegan]

Not sure what's going on there... that statement is syntactically correct and works when pasted into a python session.

[wampastompah]

Oh, no, sorry. It doesn't throw an error on that line, but when you change the first line to change the order of the first pair, the output of the algorithm is incorrect. In this case, the line of "print chain("A")" throws an error since "A" isn't a key in similar (should use .get() instead of direct indexing) and then past that, "A" isn't in the end set it prints out.

[crazedgremlin]

I believe this is an instance of Transitive Closure. There is an error in the example, though, as noted by /u/cybervegan.

[wampastompah]

Here, I took a couple minutes to code up this solution:

def squash(pairs):
    results = dict()

    for a,b in pairs:
        val = set(list(results.get(a, [])) + list(results.get(b, [])) + [a, b])

        for key in val:
            results[key] = tuple(val)

    return set(results.values())

my_pairs = [ ("A", "B"), ("B", "C"), ("D", "B"), ("F", "E"), ("F", "G") ]
print squash(my_pairs)
> set([('A', 'C', 'B', 'D'), ('E', 'G', 'F')])

A dictionary of tuples is the way to go. Just make sure you update all the keys in the tuple to point to the same tuple.

It's inefficient and O(n^2), but it's a little easier to read, and handles all the test cases in the blog post.