回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>编辑:新问题。考虑到我怀疑这个问题比我原先想象的要困难——可能是NP复杂,我有一个不同的问题:什么是有用的算法,可以接近最大化使用的字母数?在</p>
<p>我受启发写了一个基于纸牌游戏拼字大满贯的程序!不过,我对算法还不熟悉,想不出解决这个问题的有效方法:</p>
<p>以一个包含英语有效的4个字母单词的字符串开头。你可以一次把一个字母放在那个单词上,这样通过放置这个字母,你就形成了一个新的字典中的有效单词。你的字母与字母表中的字母相等。在</p>
<p>例如,如果起始词是“cart”,则这可能是一个有效的移动序列:</p>
<p>沙子-->;正常-->;正弦-->;直线-->;lins-->;引脚-->fins,等等</p>
<p>目标是通过使用尽可能多的字母表中的字母(不使用一个字母多次)来最大限度地增加序列中单词的数量。在</p>
<p>我的算法找不到最长的序列,只是猜测最长的可能是什么。在</p>
<p>首先,它得到所有单词的列表,这些单词可以通过改变起始单词的一个字母组成。这个列表称为“adjacentList”,然后它会查看adjacentList中的所有单词,并找出其中哪个单词的相邻单词最多。无论哪个单词的邻接词最多,它都会选择将起始词变成。在</p>
<p>例如,sane这个词可以换成28个词,sine这个词可以变成27个其他词,line这个词可以变成30个其他词--每一个选择都是为了最大限度地提高拼写越来越多单词的可能性。在</p>
<p>解决这个问题最好的办法是什么?什么样的数据结构是最佳的?如何改进我的代码,使其更高效、更不冗长?在</p>
<pre><code>##Returns a list of all adjacent words. Lists contain tuples of the adjacent word and the letter that
##makes the difference between those two words.
def adjacentWords(userWord):
adjacentList, exactMatches, wrongMatches = list(), list(), str()
for dictWords in allWords:
for a,b in zip(userWord, dictWords):
if a==b: exactMatches.<a href="https://www.cnpython.com/list/append" class="inner-link">append</a>(a)
else: wrongMatches = b
if len(exactMatches) == 3:
adjacentList.append((dictWords, wrongMatches))
exactMatches, wrongMatches = list(), list()
return adjacentList
#return [dictWords for dictWords in allWords if len([0 for a,b in zip(userWord, dictWords) if a==b]) == 3]
def adjacentLength(content):
return (len(adjacentWords(content[0])), content[0], content[1])
#Find a word that can be turned into the most other words by changing one letter
def maxLength(adjacentList, startingLetters):
return max(adjacentLength(content) for content in adjacentList if content[1] in startingLetters)
def main():
startingWord = "sand"
startingLetters = "a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z".replace(" ", "").split(',')
existingWords = list()
while True:
adjacentList = adjacentWords(startingWord)
letterChoice = maxLength(adjacentList, startingLetters)
if letterChoice[1] not in existingWords:
print "Going to use letter: "+ str(letterChoice[2]) + " to spell the word "+ str(letterChoice[1]) + " with "+ str(letterChoice[0]) + " possibilities."
existingWords.append(letterChoice[1])
startingLetters.remove(str(letterChoice[2]))
startingWord = letterChoice[1]
main()
</code></pre>