BFS, wanting to find the longest path between nodes, decreasing the findchildren method

Question

I opened another thread specifically with this topic, but I think I wrote too much code, and I really did not know where my problem is, now I think I have an idea, but I still need help. We have a text file with 3 letters, only 3 letters. I also have Word (node) and a queue class. It is assumed that my search method will find for one word all the children this word, say, I enter the "fan", then I should get something like ["kan", "man" .... etc]. The code currently looks 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

, findchildren , ( bfs-search), , , . , , ? - :

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

, - , " ".

def findchildren3(mangd,parent):
    children=defaultdict(list)
    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:
                children[0].append(word)
            if i>2:
                break
    return children

Answer 1

( O (n ^ 2), ), , :

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

:

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']})

---

:

import itertools
from collections import defaultdict

words = ['abc', 'def', 'adf', 'adc', 'acf', 'dec']

# Build a map of {word: {bigrams}} i.e. {'abc': {'ab', 'ba', 'bc', 'cb', 'ac', 'ca'}}
bigramMap = {k: {''.join(x) for x in itertools.permutations(k, 2)} for k in words}

# 'Invert' the map so it is {bigram: {words}} i.e. {'ab': {'abc', 'bad'}, 'bc': {...}}
wordMap = defaultdict(set)
for word, bigramSet in bigramMap.iteritems():
    for bigram in bigramSet:
        wordMap[bigram].add(word)

# Create a final map of {word: {words}} i.e. {'abc': {'abc', 'bad'}, 'bad': {'abc', 'bad'}}
result = defaultdict(set)
for k, v in wordMap.iteritems():
    for word in v:
        result[word] |= v ^ {word}

# Display all 'childen' of each word from the original list
for word in words:
    print "The 'children' of word {} are {}".format(word, result[word])

:

The 'children' of word abc are set(['acf', 'adc'])
The 'children' of word def are set(['adf', 'dec'])
The 'children' of word adf are set(['adc', 'def', 'acf'])
The 'children' of word adc are set(['adf', 'abc', 'dec', 'acf'])
The 'children' of word acf are set(['adf', 'abc', 'adc'])
The 'children' of word dec are set(['adc', 'def'])

Answer 2

( O (n ^ 2)) Python 3 ( ):

import defaultdict

words = ['fan', 'ban', 'fbn', 'ana', 'and', 'ann']

def isChildOf(a, b):
    return sum(map(lambda xy: xy[0] == xy[1], zip(a, b))) >= 2

result = defaultdict(set)
for word in words:
    result[word] = {x for x in words if isChildOf(word, x) and x != word}

# Display all 'childen' of each word from the original list
for word in words:
    print("The children of word {0} are {1}".format(word, result[word]))

:

The 'children' of word fan are set(['ban', 'fbn'])
The 'children' of word ban are set(['fan'])
The 'children' of word fbn are set(['fan'])
The 'children' of word ana are set(['and', 'ann'])
The 'children' of word and are set(['ann', 'ana'])
The 'children' of word ann are set(['and', 'ana'])

, .

isChildOf :

• zip a b , , "" . , a - 'fan', b - 'ban', zip('fan', 'ban') [('f', 'b'), ('a', 'a'), ('n', 'n')]

• map, ( ) , . (.. 'f' 'b') True, , False . [False, True, True], , .

• , sum , 2. , True 1 Python False 0, 2. , 2.

for word in words , isChildOf True, , .

, !