字母和递归

Question

我差不多完成了我的程序,但我犯了一个微妙的错误.我的程序应该接受一个字,并且通过一次更改一个字母,最终应该以指定的步数达到目标字.我一直在尝试寻找相似之处,例如:如果找到了这个词,并且目标词丢失了,这就是我的程序将以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

两者之间的区别在于,第一个检查查找的每个变体与丢失的字母.含义:lind,fond,fisd和fine.然后,如果它找到一个带有查找功能的工作单词,它会调用该新单词的变换.

与我的新程序相反,后者使用字母表中的每个字母检查查找的每个变体.

我似乎无法使此代码工作.我通过简单地打印结果的结果来测试它:

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)的原因.

我认为我的问题是我需要改变来贯穿持有人列表中的每个单词,我不知道该怎么做.虽然这只是猜测.

任何帮助,将不胜感激,

干杯.

Answer 1

我可能会对你需要的东西感到有些困惑,但是借用这篇文章,我相信我有一些应该有用的代码.

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

这有足够的帮助吗？我认为你的代码可以通过将任务分成更小的块来真正受益.