python - 字母表和递归

我几乎完成了我的程序，但我犯了一个微妙的错误。我的程序应该输入一个单词，通过一次更改一个字母，最终应该在指定的步骤数内达到目标单词。一开始我一直试图寻找相似之处，例如:如果找到了这个词，而目标词丢失了，我的程序将如何分 4 个步骤输出:

['find','fine','line','lone','lose]

这实际上是我想要的输出。但是如果你考虑一组更难的词，比如 Java 和 work，输出应该是 6 个步骤。

['java', 'lava', 'lave', 'wave', 'wove', 'wore', 'work']

所以我的错误是我没有意识到你可以通过使用目标词或原始词中不存在的字母来找到目标词。

这是我的原始代码:

import string
def changeling(word,target,steps):
    alpha=string.ascii_lowercase
    x=word##word and target has been changed to keep the coding readable.
    z=target
    if steps==0 and word!= target:##if the target can't be reached, return nothing.
        return []
    if x==z:##if target has been reached.
        return [z]


    if len(word)!=len(target):##if the word and target word aren't the same length print error.
        print "error"
        return None
    i=1
    if lookup
    if lookup(z[0]+x[1:]) is True and z[0]+x[1:]!=x :##check every letter that could be from z, in variations of, and check if they're in the dictionary.
        word=z[0]+x[1:]
    while i!=len(x):
        if lookup(x[:i-1]+z[i-1]+x[i:]) and x[:i-1]+z[i-1]+x[i:]!=x:
            word=x[:i-1]+z[i-1]+x[i:]

        i+=1
    if lookup(x[:len(x)-1]+z[len(word)-1]) and x[:len(x)-1]+z[len(x)-1]!=x :##same applies here.
        word=x[:len(x)-1]+z[len(word)-1]


    y =  changeling(word,target,steps-1)
    if y :
      return [x] + y##used to concatenate the first word to the final list, and if the list goes past the amount of steps.
    else:
      return None

这是我当前的代码:

import string
def changeling(word,target,steps):
    alpha=string.ascii_lowercase
    x=word##word and target has been changed to keep the coding readable.
    z=target
    if steps==0 and word!= target:##if the target can't be reached, return nothing.
        return []
    if x==z:##if target has been reached.
        return [z]
    holderlist=[]


    if len(word)!=len(target):##if the word and target word aren't the same length print error.
        print "error"
        return None
    i=1
    for items in alpha:

        i=1
        while i!=len(x):
            if lookup(x[:i-1]+items+x[i:]) is True and x[:i-1]+items+x[i:]!=x:
                word =x[:i-1]+items+x[i:]
                holderlist.append(word)

            i+=1
        if lookup(x[:len(x)-1]+items) is True and x[:len(x)-1]+items!=x:
            word=x[:len(x)-1]+items
            holderlist.append(word)

    y =  changeling(word,target,steps-1)
    if y :
      return [x] + y##used to concatenate the first word to the final list, and if the/
   list goes past the amount of steps.
    else:
      return None

两者之间的区别在于，第一个检查 find 的每个变体都使用来自 loss 的字母。含义:lind、喜欢、fisd 和罚款。然后，如果它使用查找功能找到一个工作单词，它会调用这个新找到的单词的转换。

与我的新程序相反，它用字母表中的每个字母检查 find 的每个变体。

我似乎无法让这段代码工作。我通过简单地打印发现的结果来测试它:

for items in alpha:

        i=1
        while i!=len(x):
             print (x[:i-1]+items+x[i:])

             i+=1
        print (x[:len(x)-1]+items)

这给出:

aind
fand
fiad
fina
bind
fbnd
fibd
finb
cind
fcnd
ficd
finc
dind
fdnd
fidd
find
eind
fend
fied
fine
find
ffnd
fifd
finf
gind
fgnd
figd
fing
hind
fhnd
fihd
finh
iind
find
fiid
fini
jind
fjnd
fijd
finj
kind
fknd
fikd
fink
lind
flnd
fild
finl
mind
fmnd
fimd
finm
nind
fnnd
find
finn
oind
fond
fiod
fino
pind
fpnd
fipd
finp
qind
fqnd
fiqd
finq
rind
frnd
fird
finr
sind
fsnd
fisd
fins
tind
ftnd
fitd
fint
uind
fund
fiud
finu
vind
fvnd
fivd
finv
wind
fwnd
fiwd
finw
xind
fxnd
fixd
finx
yind
fynd
fiyd
finy
zind
fznd
fizd
finz

这是完美的!请注意，字母表中的每个字母都至少经过我的单词一次。现在，我的程序所做的是使用一个辅助函数来确定该词是否在我得到的字典中。

考虑到这一点，而不是像我的第一个程序那样，我现在收到多个合法的单词，除非当我执行 word=foundword 时，这意味着我每次都替换前一个单词。这就是我尝试使用holderlist.append(word) 的原因。

我认为我的问题是我需要转换来遍历持有者列表中的每个单词，但我不知道该怎么做。虽然这只是猜测。

任何帮助，将不胜感激，

干杯。

最佳答案

我可能对您需要什么有点困惑，但是通过从 this post 借用，我相信我有一些应该有用的代码。

>>> alphabet = 'abcdefghijklmnopqrstuvwxyz'
>>> word = 'java'
>>> splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
>>> splits
[('', 'java'), ('j', 'ava'), ('ja', 'va'), ('jav', 'a'), ('java', '')]
>>> replaces = [a + c + b[1:] for a, b in splits for c in alphabet if b]
>>> replaces
['aava', 'bava', 'cava', 'dava', 'eava', 'fava', 'gava', 'hava', 'iava', 'java', 'kava', 'lava', 'mava', 'nava', 'oava', 'pava', 'qava', 'rava', 'sava', 'tava', 'uava', 'vava', 'wav
a', 'xava', 'yava', 'zava', 'java', 'jbva', 'jcva', 'jdva', 'jeva', 'jfva', 'jgva', 'jhva', 'jiva', 'jjva', 'jkva', 'jlva', 'jmva', 'jnva', 'jova', 'jpva', 'jqva', 'jrva', 'jsva', '
jtva', 'juva', 'jvva', 'jwva', 'jxva', 'jyva', 'jzva', 'jaaa', 'jaba', 'jaca', 'jada', 'jaea', 'jafa', 'jaga', 'jaha', 'jaia', 'jaja', 'jaka', 'jala', 'jama', 'jana', 'jaoa', 'japa'
, 'jaqa', 'jara', 'jasa', 'jata', 'jaua', 'java', 'jawa', 'jaxa', 'jaya', 'jaza', 'java', 'javb', 'javc', 'javd', 'jave', 'javf', 'javg', 'javh', 'javi', 'javj', 'javk', 'javl', 'ja
vm', 'javn', 'javo', 'javp', 'javq', 'javr', 'javs', 'javt', 'javu', 'javv', 'javw', 'javx', 'javy', 'javz']

一旦你有所有可能的替换列表，你就可以简单地做

valid_words = [valid for valid in replaces if lookup(valid)]

这应该为您提供可以通过替换单词中的 1 个字符形成的所有单词。通过将此代码放在一个单独的方法中，您可以获取一个单词，从该当前单词中获取可能的下一个单词，然后对每个单词进行递归。例如:

alphabet = 'abcdefghijklmnopqrstuvwxyz'
def next_word(word):
    splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
    replaces = [a + c + b[1:] for a, b in splits for c in alphabet if b]
    return [valid for valid in replaces if lookup(valid)]

这是足够的帮助吗？我认为您的代码可以通过将任务分成更小的块而真正受益。

关于python - 字母表和递归，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9913067/