Python Question
BFS, wanting to find the longest path between nodes, reducing the findchildren-method
I've opened another thread with exactly this subject, but I think I posted too much code and I didn't really know where my problem was, now I think I have a better idea but still in need of help. What we have is a text-file with 3 letter words, only 3 letter words. I also have a Word (node) and queue-class. My findchildren-method is supposed to find, for one single word, all the children to this word, let's say I enter "fan", then I'm supposed to get something like ["kan","man"....etc]. The code is currently looking like this:
def findchildren(mangd,parent):
children=set()
lparent=list(parent)
mangd.remove(parent)
for word in mangd:
letters=list(word)
count=0
i=0
for a in letters:
if a==lparent[i]:
count+=1
i+=1
else:
i+=1
if count==2:
if word not in children:
children.add(word)
if i>2:
break
return children
The code above, for findchildren is currently working fine, but, when I use it for my other methods (to implement the bfs-search) everything will take way too long time, therefore, I would like to gather all the children in a dictionary containing lists with the children. It feels like this assignment is out of my league right now, but is this possible to do? I tried to create something like this:
def findchildren2(mangd):
children=[]
for word in mangd:
lparent=list(word)
mangd.remove(word)
letters=list(word)
count=0
i=0
for a in letters:
if a==lparent[i]:
count+=1
i+=1
else:
i+=1
if count==2:
if word not in children:
children.append(word)
if i>2:
break
return children
I suppose my last try is simply garbage, I get the errormessage " Set changed size using iteration".
Recommended for you: Get network issues from WhatsUp Gold. Not end users.
Answer Source
There are more efficient ways to do this (the below is O(n^2) so not great) but here is a simple algorithm to get you started:
import itertools
from collections import defaultdict
words = ['abc', 'def', 'adf', 'adc', 'acf', 'dec']
bigrams = {k: {''.join(x) for x in itertools.permutations(k, 2)} for k in words}
result = defaultdict(list)
for k, v in bigrams.iteritems():
for word in words:
if k == word:
continue
if len(bigrams[k] & bigrams[word]):
result[k].append(word)
print result
Produces:
defaultdict(<type 'list'>, {'abc': ['adc', 'acf'], 'acf': ['abc', 'adf', 'adc'], 'adf': ['def', 'adc', 'acf'], 'adc': ['abc', 'adf', 'acf', 'dec'], 'dec': ['def', 'adc'], 'def': ['adf', 'dec']})
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download