アルファベットと再帰

Question

私のプログラムはほとんど終わりましたが、私は微妙な間違いをしました。私のプログラムは言葉を取り、一度に1文字ずつ変更することで、最終的に指定されたステップ数で目標単語に到達することになっています。単語が見つけた場合は、ターゲットワードが負け、どのように私のプログラムは4つの段階で出力だろうここにあります：私は、例えば、類似点を探すために最初にしようとしていた実際に私が欲しかった出力である

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

。しかし、Javaや仕事のように厳しい言葉を考えると、出力は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 

両者の違いは、最初にチェックすることを失うからの手紙で見つけるのすべてのバリエーションです。意味：嘘つき、嘘つき、詐欺、罰金。次に、ルックアップ関数を使用して動作中の単語を見つけたら、その新しい単語でチェンジリングを呼び出します。

アルファベットのすべての1文字で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）を試しています。

私の問題はホルダーリストの各単語を実行するためにチェンジリングする必要があることだと思います。どうすればいいのか分かりません。それは推測だけですが。

すべてのヘルプは、

乾杯をいただければ幸いです。

Answer 1

私はあなたが必要とするものについて少し混乱するかもしれませんが、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'] 

あなたはすべての可能な置き換えのリストを持っていたら、あなたは、単にあなたの言葉で1つの文字を置き換えることによって形成することができるすべての単語を与える必要があり

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

を行うことができます。このコードを別の方法で配置することによって、単語を取り、その現在の単語から次の単語を取得し、それぞれの単語を再帰させることができます。例：

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

これで十分ですか？私はあなたのコードが本当に小さなチャンクにタスクを分離することによって利益を得ることができると思います。

Answer 2

はあなたのコードを修正：

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. 
     raise BaseException("Starting word and target word not the same length: %d and %d" % (len(word), 
    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(pos_word, target, steps-1) for pos_word in holderlist] 
    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 

どこlen(word)とlen(target)、W/Oスタックトレースと致命的でない、あいまいな印刷何かよりも例外を発生させる方が良いと思います。

スラッシュ（/）ではなく、バックスラッシュ（\）を使用して行を継続します。そして、彼らはコメントには作用しません。