identifying pairwise groups from dictionary

Question

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)

Answer 1

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.