Рекурсия и добавление в списки - PullRequest
Новая
       14

Рекурсия и добавление в списки

3 голосов
/ 26 марта 2012

У меня проблемы с программой, программа берет одно слово, и меняя одну букву за раз, преобразует это слово в целевое слово. Хотя имейте в виду, что преобразованное слово должно быть законным словом в соответствии со словарем слов, которые мне дали.

Мне трудно понять, как сделать это рекурсивным. Программа имеет ограничение на количество шагов, которые она должна предпринять.

Вывод должен быть списком. Так что, если параметры для смены функции
changeling («найти», «потерять»), вывод должен быть: [ 'Найти', 'прекрасный', 'строка', 'одинокий', 'потерять'].

с моим текущим кодом: 

def changeling(word,target,steps):
holderlist=[]
i=0
if steps<0 and word!=target:
    return None

if steps!=-1:
    for items in wordList:
        if len(items)==len(word):
            i=0

            if items!=word:
                for length in items:

                    if i==1:
                        if items[1]==target[1] and items[0]==word[0] and items[2:]==word[2:]:
                            if items==target:
                                print "Target Achieved"
                                holder.list.append(target)
                            holderlist.append(items)
                            holderlist.append(changeling(items,target,steps-1))


                    elif i>0 and i<len(word)-1 and i!=1:
                        if items[i]==target[i] and items[0:i]==word[0:i] and items[i+1:]==word[i+1:]:
                            if items==target:
                                print "Target Achieved"
                            holderlist.append(items)
                            holderlist.append(changeling(items,target,steps-1))


                    elif i==0:
                        if items[0]==target[0] and items[1:]==word[1:]:
                            if items==target:
                                print "Target Achieved"
                            holderlist.append(items)
                            holderlist.append(changeling(items,target,steps-1))


                    elif i==len(word)-1:
                        if items[len(word)-1]==target[len(word)-1] and items[0:len(word)-1]==word[0:len(word)-1]:
                            if items==target:
                                print "Target Achieved"
                            holderlist.append(items)
                            holderlist.append(changeling(items,target,steps-1))

                    else:
                        return None

                    i+=1

return holderlist

Я получаю грязный вывод: ['fine', ['line', ['lone', ['lost', []]]], 'fond', []]

Я получил ответ, который хотел, но я не уверен, как а) очистить его, не имея списков в списках. и б) появляется «фонд», потому что когда вызывается метод «найти», он дает «хорошо» и «фонд», «хорошо» - это тот, который заканчивается целевым словом, а «фонд» не удается, но я не уверен, как избавиться от него после добавления это к списку владельцев.

Любая помощь будет оценена.

Приветствие.

Ответы [ 3 ]

3 голосов
/ 26 марта 2012

Я не совсем уверен, что использование extend вместо append решит все ваши проблемы, потому что кажется, что это может не учитывать внесение изменений, которые не приводят к решению слова и требуют возврата.

Если выяснится, что я прав, а другие ответы не работают, вот рекурсивная функция, которая преобразует ваш текущий результат в то, что вы ищете: 

def flatten_result(nested_list, target):
    if not nested_list:
        return None
    for word, children in zip(nested_list[::2], nested_list[1::2]):
        if word == target:
            return [word]
        children_result = flatten_result(children, target)
        if children_result:
            return [word] + children_result
    return None

>>> result = ['fine', ['line', ['lone', ['lose', []]]], 'fond', []]
>>> flatten_result(result, 'lose')
['fine', 'line', 'lone', 'lose']
3 голосов
/ 26 марта 2012

Если вы пытаетесь добавить список в список, вы, вероятно, хотите extend вместо append.

http://docs.python.org/library/stdtypes.html#mutable-sequence-types

1 голос
/ 26 марта 2012

Вот альтернативная реализация. Он не использует рекурсию, а перестановки. Он был переписан, чтобы передавать список слов, а не полагаться на глобальный список слов, что должно сделать его более переносимым. Эта реализация опирается также и на генераторы, что обеспечивает меньший объем памяти, чем расширение списков (как в решении расширения / добавления) 

import itertools

somelists = [['find','fine','line','lone','lose'],
            ['bank','hank','hark','lark','lurk'],
            ['tank','sank','sink','sing','ding']]

def changeling(word, target, wordlist):
    def difference(word, target):
        return len([i for i in xrange(len(word)) if word[i] != target[i]])

    for length in xrange(1, len(wordlist) + 1):
        for possibilities in [j for j in itertools.permutations(wordlist, length) if j[0] is word and j[-1] is target]:
            #computes all permutations and discards those whose initial word and target word don't match parameters
            if all(difference(possibilities[i], possibilities[i+1]) == 1 for i in xrange(0, len(possibilities) - 1)):
                #checks that all words are exactly one character different from previous link
                return possibilities
                #returns first result that is valid; this can be changed to yield if you wish to have all results

for w in somelists:
    print "from '%s' to '%s' using only %s" % (w[-2], w[0], w)
    print changeling(w[-2], w[0], w)
    print

w[-2], w[0] может быть изменено / заменено для соответствия любым выбранным вами словам

...