4

I have set of pairwise relationship something like this

col_combi = [('a','b'), ('b','c'), ('d','e'), ('l','j'), ('c','g'), 
             ('e','m'), ('m','z'), ('z','p'), ('t','k'), ('k', 'n'), 
             ('j','k')]

Number of such relationship is big enough to check it individually. These tuple indicates that both values are same. I would like to apply transitivity and find out common groups. Output would be like following:

[('a','b','c','g'), ('d','e','m','z','p'), ('t','k','n','l','j')]

I tried following code but it has bug,

common_cols = []
common_group_count = 0

for (c1, c2) in col_combi:
    found = False
    for i in range(len(common_cols)):
        if (c1 in common_cols[i]):
            common_cols[i].append(c2)
            found = True
            break
        elif (c2 in common_cols[i]):
            common_cols[i].append(c1)
            found = True
            break
    if not found:
        common_cols.append([c1,c2])

Output of above code is following

[['a', 'b', 'c', 'g'], ['d', 'e', 'm', 'z', 'p'], ['l', 'j', 'k'], ['t', 'k', 'n']]

I know why this code is not working. So I would like to know how can I perform this task.

Thanks in advance

3
  • looks like a union-find problem: en.wikipedia.org/wiki/Disjoint-set_data_structure
    – yurib
    Commented Sep 16, 2015 at 9:45
  • You may like this python-dictionary-of-sets
    – luoluo
    Commented Sep 16, 2015 at 9:54
  • 2
    You need to specify whether you want to preserve the tuple ordering in your output "chain". i.e. does the output need to be as you present [('a','b','c','g'), ('d','e','m','z','p'), ('t','k','n','l','j')] (tuple ordering preserved) or is that entirely equivalent to (e.g.) [('a','c','g','b'), ('d','e','m','z','p'), ('t','l','j','k','n')] for you? Commented Sep 16, 2015 at 10:35

4 Answers 4

9

You can approach this as a graph problem using the NetworkX library:

import networkx

col_combi = [('a','b'), ('b','c'), ('d','e'), ('l','j'), ('c','g'), 
             ('e','m'), ('m','z'), ('z','p'), ('t','k'), ('k', 'n'), 
             ('j','k')]

g = networkx.Graph(col_combi)

for subgraph in networkx.connected_component_subgraphs(g):
    print subgraph.nodes()

Output:

['m', 'z', 'e', 'd', 'p']
['t', 'k', 'j', 'l', 'n']
['a', 'c', 'b', 'g']
0
4

You can implement a solution using sets and union/intersection operations.

col_combi = [('a','b'), ('b','c'), ('d','e'), ('l','j'), ('c','g'), 
             ('e','m'), ('m','z'), ('z','p'), ('t','k'), ('k', 'n'), 
             ('j','k')]

from itertools import combinations

sets = [set(x) for x in col_combi]

stable = False
while not stable:                        # loop until no further reduction is found
    stable = True
    # iterate over pairs of distinct sets
    for s,t in combinations(sets, 2):
        if s & t:                        # do the sets intersect ?
            s |= t                       # move items from t to s 
            t ^= t                       # empty t
            stable = False

    # remove empty sets
    sets = list(filter(None, sets)) # added list() for python 3

print sets

Output:

[set(['a', 'c', 'b', 'g']), set(['p', 'e', 'd', 'z', 'm']), set(['t', 'k', 'j', 'l', 'n'])]

Note: doc for itertools.combinations

9
  • Did he really want that? Commented Sep 16, 2015 at 10:04
  • Your code is giving me unique values over list of list. Are you sure you understood my problem?
    – vrajs5
    Commented Sep 16, 2015 at 10:06
  • @vrajs5 I fixed the solution
    – wap26
    Commented Sep 16, 2015 at 10:13
  • @wap26 - I don't know but code is working well with 2.7.2 but giving me <filter object at 0x7fee21d81400> in python 3
    – vrajs5
    Commented Sep 16, 2015 at 10:25
  • @vrajs5: Change sets = filter(None, sets) to sets = list(filter(None, sets))
    – PM 2Ring
    Commented Sep 16, 2015 at 10:29
1

A solution with itertools, you can take a look.

lst =[]
import itertools
for a, b in itertools.combinations(col_combi, 2):
    for i in a:
        if i in b:
            lst.append(set(a+b))



for indi,i in enumerate(lst):
    for j in lst:
        if i == j:
            continue
        if i & j:
            lst[indi] = i|j
            lst.remove(j)


print lst

Output of this is:

[set(['a', 'c', 'b', 'g']), set(['k', 'j', 'l', 'n']), set(['e', 'd', 'm', 'p', 'z'])]

Of course this can be made more efficient. I will try to update soon.

0

From the code after elif you assume the relationship is reflexive. Your algorithm fails if the pairs are not provided in a specific order.

Example:

(b, c) (a, b) (c, d)

will end up with two sets

b, c, d

and

a, b

The problem is about partitioning a set using an equivalence relation. Understanding the set theory background helps identifying a library that can solve the problem. See https://en.m.wikipedia.org/wiki/Equivalence_relation .

5
  • Yes. I found why it is not working, before posting it here.
    – vrajs5
    Commented Sep 16, 2015 at 9:49
  • @vrajs5: You should have mentioned that important information in the question.
    – PM 2Ring
    Commented Sep 16, 2015 at 10:38
  • @vrajs5: I did read the bold letters, so I knew that you knew why your algorithm was defective. But you didn't tell us why it was defective. It would've been helpful if you'd said something like what Tarik has mentioned in this answer. Anyway, it's no big deal.
    – PM 2Ring
    Commented Sep 17, 2015 at 11:10
  • @PM2Ring He knew that you knew that he knew why his algorithm was defective...lol. Just kidding :-)
    – Tarik
    Commented Sep 17, 2015 at 19:28
  • I knew you were going to say that. ;-)
    – PM 2Ring
    Commented Sep 18, 2015 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.