python – BFS,想要找到节点之间最长的路径,减少了findchildren方法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python – BFS,想要找到节点之间最长的路径,减少了findchildren方法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3264字,纯文字阅读大概需要5分钟。
内容图文
![python – BFS,想要找到节点之间最长的路径,减少了findchildren方法](/upload/InfoBanner/zyjiaocheng/767/9e293acc6562478e9e8abf67b855e714.jpg)
我已经打开了另一个主题正是这个主题,但我认为我发布了太多的代码,我不知道我的问题在哪里,现在我觉得我有更好的想法,但仍然需要帮助.我们所拥有的是一个包含3个字母单词的文本文件,只有3个字母单词.我还有一个Word(节点)和队列类.我的findchildren方法应该为一个单词找到所有孩子这个词,让我说我进入“粉丝”,然后我应该得到类似[“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
上面的代码,对于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
解决方法:
有更有效的方法来做到这一点(下面是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'])
内容总结
以上是互联网集市为您收集整理的python – BFS,想要找到节点之间最长的路径,减少了findchildren方法全部内容,希望文章能够帮你解决python – BFS,想要找到节点之间最长的路径,减少了findchildren方法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。