PYTHON给出了一个起始单词，哪个字母序列将允许您最大化可以拼写的有效单词的数量

Question

编辑：新问题。考虑到我怀疑这个问题比我原先想象的要困难——可能是NP复杂，我有一个不同的问题：什么是有用的算法，可以接近最大化使用的字母数？在

我受启发写了一个基于纸牌游戏拼字大满贯的程序！不过，我对算法还不熟悉，想不出解决这个问题的有效方法：

以一个包含英语有效的4个字母单词的字符串开头。你可以一次把一个字母放在那个单词上，这样通过放置这个字母，你就形成了一个新的字典中的有效单词。你的字母与字母表中的字母相等。在

例如，如果起始词是“cart”，则这可能是一个有效的移动序列：

沙子-->；正常-->；正弦-->；直线-->；lins-->；引脚-->fins，等等

目标是通过使用尽可能多的字母表中的字母（不使用一个字母多次）来最大限度地增加序列中单词的数量。在

我的算法找不到最长的序列，只是猜测最长的可能是什么。在

首先，它得到所有单词的列表，这些单词可以通过改变起始单词的一个字母组成。这个列表称为“adjacentList”，然后它会查看adjacentList中的所有单词，并找出其中哪个单词的相邻单词最多。无论哪个单词的邻接词最多，它都会选择将起始词变成。在

例如，sane这个词可以换成28个词，sine这个词可以变成27个其他词，line这个词可以变成30个其他词--每一个选择都是为了最大限度地提高拼写越来越多单词的可能性。在

解决这个问题最好的办法是什么？什么样的数据结构是最佳的？如何改进我的代码，使其更高效、更不冗长？在

##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.append(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()

Answer 1

@解析语言 你可能会发现，虽然对于给定的任务有一个最优的解决方案，但是没有一个已知的以最优方式解决它的方法。此任务是NP-class问题之一。在

考虑一下这个：

sand  > [?]and 

此时，您必须遍历[?]and的所有可能的组合，以找出符合条件的单词。在最坏的情况下，没有启发式，那就是26次迭代。在

^{pr2}$

现在，取每个找到的单词，重复第二个字母等。
您可以看到，您必须进行的迭代量呈指数级增长。在

这在某种程度上与国际象棋问题非常相似。不管你的电脑有多强大，它都不能预测所有可能的动作，因为组合太多了。在

Answer 2

我和一个朋友在一个数据结构和算法课程的实验中开发了一个类似的程序（虽然是用Java编写的）。任务是创建从一个单词到另一个单词的最短单词链。在

我们建立了一棵所有可用单词的树，其中一个节点连接到另一个节点，如果它们只相差一个字母。为了提高速度，需要使用某种哈希表，比如字典。实际上，我们从用作键的单词中删除了一个字母，这样就利用了连接词具有相同哈希的事实，但是如果没有代码，很难解释。在

为了找到最短的链，我们使用了宽度优先搜索。然而，在图中找到最短路径比最长路径容易。有关详细信息，请参见longest path problem。在

要解决主要问题，您可以遍历所有单词。然而，如果速度很重要的话，通常更容易找到一个好的特殊启发式算法。在