# identifying pairwise groups from dictionary

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)

• 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. – GZ0 Oct 2 '19 at 1:47

# 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.

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