BFS，想找到节点之间的最长路径，缩减findchildren方法。

Question

我已经开了另一个帖子，主题正是这个问题，但我认为我贴了太多的代码，而且我真的不知道我的问题在哪里，现在我觉得我有了更好的想法，但仍然需要帮助。我们有一个文本文件，里面只有3个字母的单词。我还有一个Word（节点）和队列类。我的findchildren方法应该找到一个单词的所有子级，比如我输入“fan”，那么我应该得到["kan"，“man” ....等]这样的东西。目前的代码看起来像这样：

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

上面的代码，用于查找子节点，目前工作正常，但是当我将其用于其他方法（实现广度优先搜索）时，所有操作都需要太长时间，因此，我想收集包含子节点列表的字典中的所有子节点。现在感觉这个任务超出了我的能力范围，但这个可行吗？我尝试创建了如下内容：

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

- Krantz

---

你能准确地定义“将所有子项与此单词相关联”吗？从你的例子中，它似乎适用于长度为2的常见后缀？同时，我们需要示例输入/输出。 - FujiApple

将所有的单词转换为“fan”，就是指在我的txt文件中，将所有的单词转换为“fan”。一个单词被称为“fan”的孩子，是指与“fan”共享两个字母的每个单词。这些都是瑞典语单词，它们共享两个相同字母的顺序并不重要，例如，“fbn”也可以。但是我的txt文件中没有包含这个单词。我想要的输出是一个包含所有单词孩子列表的字典。我希望能够通过从这个字典中收集孩子而不是一直调用findchildren来加快我的其他方法的速度。 - Krantz

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

- FujiApple

---

非常感谢您的帮助，我会尝试将此实现到我的BFS中，并看看是否能够使其更加有效，目前它非常慢。 - Krantz

如果我想要调用“abc”的子元素，有没有简单的方法可以做到这一点？ - Krantz

为了让它更快，需要反转字典，使其映射为 二元组 -> 单词列表 [word]，即 {'ab': ['abc', 'abd', 'acb']}，然后你就可以在列表中找到所有具有两个共同字母的单词。 - FujiApple

fbn 会被认为是一个子字符串吗？因为它们在匹配位置上共享了两个字母，或者它们必须是连续的字母？ - FujiApple

是的，“fbn”将是一个子级，但例如，“ana”不应该是“fan”的子级。它们不必按顺序排列，但它们必须处于正确的位置。 - Krantz

Answer 2

针对 Python 3 中更新的要求，以下是解决方案（不幸的是，它的时间复杂度为 O(n^2)）（在此处运行here）：

from collections 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 函数接受两个单词作为输入，并执行以下操作：

1. 将zip函数的参数a和b一起处理，这两个参数都被视为可迭代对象，每个字符在迭代中被视为一个“项”。例如，如果a是'fan'，b是'ban'，那么zip('fan', 'ban')会生成以下配对列表：[('f', 'b'), ('a', 'a'), ('n', 'n')]

2. 接下来使用map函数将lambda函数（匿名函数的花哨名称）应用于步骤1中生成的列表中的每个项。该函数只需取输入元素对（即'f'和'b'）并返回True（如果它们匹配）或False（否则）。对于我们的示例，这将导致[False, True, True]，因为第一对字符不匹配，但剩余的两对匹配。

3. 最后，该函数在步骤2生成的列表上运行sum函数。恰好在Python中，True评估为1，False评估为0，因此我们列表的总和为2。然后我们只需返回该数字是否大于或等于2。

for word in words 循环简单地将每个输入单词与所有其他单词进行比较，并保留其中 isChildOf 评估为 True 的单词，注意不要添加单词本身。

希望这很清楚！

- FujiApple

---

我修改了上面的内容，想看看是否可以像那样做？你的解决方案更加优雅，但我不太理解代码 :/ - Krantz

我编辑的那个方法似乎起作用了，但是我目前正在得到重复项，并且我想立即从我的列表中获取所有单词。 - Krantz

问题在于我无法运行它，isChild 函数出了点问题（请注意我使用的是 Python3）。由于我对此并不是很理解，所以这对我来说很困难。但是当我看到你的“produces”时，它似乎正好按照我想要的方式工作。 - Krantz

抱歉:/嗯，对我来说它有效，虽然不确定其工作原理，但却确实有效。 - Krantz

再次感谢，我会尝试理解您的解决方案，至少看起来比我的好多了。很抱歉没有使用python3标签，下次我会记住的。也许我会带着另一个问题回来 :) - Krantz