3
\$\begingroup\$

I have a dictionary that looks like this

masterdict = {'a':['b','c','d','e'],
         'b':['c','d','e'],
         'c':['d','e'],
         'd':['e']
         'e':[]}

where the list has all the values that are 'compatible' with the key and vice-versa. Since the dictionary is non-redundant, repeated compatiblities are not reported in the dictionary. For eg. 'e' is compatible with 'a','b','c' and 'd' but masterdict['e'] is empty since it is reported in the other lists. I would like to identify all groups of elements, such that all the elements are mutually compatible. Hence for the masterdict given above, the solution would be [['a', 'b', 'c', 'd'], ['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'e'], ['a', 'b', 'd', 'e'], ['a', 'c', 'd', 'e'], ['b', 'c', 'd', 'e']]. Not showing lists of smaller size.

masterdict = {'a':['b','d','e'],
         'b':['c','d'],
         'c':['e'],
         'd':['e'],
         'e':[] }

then the solution would be [['a', 'b', 'd'], ['a', 'd', 'e']]. I did write a recursive function to do this, but it is slow for larger dictionaries (len(list) > 1000). The code is given below. I would like some suggestions on how to write a faster version, maybe using itertools or some other module. Thanks alot

import sys
import os

def recursive_finder(p1,list1,masterdict,d,ans):
        # if lenght of d is more than 2, store that list in ans
        if len(d) >2 :
                ans.append(d)
        nextlist = []
        # if lenght of list is 0, do not do anythin
        if len(list1) == 0:
                pass
        else:
                other = []
                for i in list1:
                        if i in masterdict[p1]:
                                new = []
                                new.extend(d)
                                new.append(i)
                                other.append(new)
                                nextlist.append(i)
                for i in range(len(nextlist)):
                        p1 = nextlist[i]
                        dnew = other[i]
                        recursive_finder(p1,nextlist[i+1:],masterdict,dnew,ans)

masterdict = {'a':['b','d','e'],
         'b':['c','d'],
         'c':['e'],
         'd':['e'],
         'e':[] }

final = []
ans = []
for mainkey in masterdict:
        if len(masterdict[mainkey]) > 1:
                for i in range(len(masterdict[mainkey])):
                        p1 = masterdict[mainkey][i]
                        recursive_finder(p1,masterdict[mainkey][i+1:],masterdict,[mainkey,p1],ans)

print(ans)
\$\endgroup\$
  • 3
    \$\begingroup\$ The problem can be formulated as finding cliques in graphs. Finding maximal cliques is an NP-Complete problem. You could consider using third-party libraries such as networkx for the task. \$\endgroup\$ – GZ0 Oct 2 at 1:47
0
\$\begingroup\$

Indentation

You should use four (4) spaces for indentation, not eight (8).

Logic

This

if len(list1) == 0:
    pass
else:

should be changed to

if list:
    ... code here ...

This removes the need for the else, as you instead check if the list contains anything. Check out the Python Docs on Truth Testing.

Enumerate

This

for mainkey in masterdict:
    if len(masterdict[mainkey]) > 1:
        for i in range(len(masterdict[mainkey])):
            p1 = masterdict[mainkey][i]
            recursive_finder(p1,masterdict[mainkey][i+1:],masterdict,[mainkey,p1],ans)

can be changed to this

for mainkey in masterdict:
    if len(masterdict[mainkey]) > 1:
        for i, value in enumerate(masterdict[mainkey]):
            p1 = value
            recursive_finder(p1,masterdict[mainkey][i+1:],masterdict,[mainkey,p1],ans)

Use enumerate since you are using both the index and the value.

\$\endgroup\$
  • \$\begingroup\$ The for-loop can be changed to for mainkey, mainvalue in masterdict.items() to avoid multiple references to masterdict[mainkey]. \$\endgroup\$ – GZ0 Oct 2 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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