从字典构建字符串的递归函数

Question

我遇到了递归函数的问题。

hints = ['one','two','three', 'four']

firstCity = 'ROME'

dictionary = { 'ROMEone' : { 'PARIS' : {'hello'} , 'CAIRO': {'money'}, 'MOSCOW': {'racing'} },
           'CAIROtwo': { 'MILAN' : {'in'}},
           'PARIStwo': { 'BERLIN' : {'how'} , 'CANCUN' : {'im'} },
           'MOSCOWtwo': { 'AMSTERDAM' : {'cars'} },
           'BERLINthree': { 'AMSTERDAM' : {'are'} },
           'AMSTERDAMthree' : { 'MILAN' : {'are'} },
           'MILANthree' : { 'PARIS' : {'the'} },
           'CANCUNthree' : { 'LONDON' : {'john'}},
           'AMSTERDAMfour': { 'MILAN' : {'you'} },
           'MILANfour': { 'LONDON' : {'fast'} },
           'PARISfour': { 'CANCUN' : {'bank'} },
           'LONDONfour': { 'FLORENCE' : {'smith'}} }

该函数的作用是从“firstCity”开始在字典中查找，找到所有可能从字典中提取的词组。

字典的每个元素都有 2 个信息：目的地（去哪里看）和单词（构建我们正在寻找的短语）

结果应该是：

[ ["hello how are you" , "MILAN"],
  ["hello im john smith", 'FLORENCE"],
  ["money in the bank", "CANCUN"],
  ["racing cars are fast", "LONDON"] ]

到目前为止我想出了这个解决方案，但它不能正常工作，我可以就如何解决这个问题寻求一些建议吗？请！

def ex(dictionary, hints, firstCity, words = []):

    for key in dictionary:

        if key == (firstCity + hints[0]):

            for destination in dictionary[key]:

                firstCity = destination

                word = getValue(dictionary[key][destination])
                #getValue simply get the value from the set

                words.append(word)
                if hints[1:] == []:
                    return words
                ex(dictionary, hints[1:], firstCity,words)
    return words
    
def getValue(st):
for el in st:
    if len(st) == 1:
        return el

具有值的函数的结果将是：

['hello','how','are','you','are','fast','the','bank','im','john','smith','money','in','the','bank','racing','cars','are','fast','the','bank']

Answer 1

您可以对生成器使用递归：

hints = ['one','two','three', 'four']
d = {'ROMEone': {'PARIS': {'hello'}, 'CAIRO': {'money'}, 'MOSCOW': {'racing'}}, 'CAIROtwo': {'MILAN': {'in'}}, 'PARIStwo': {'BERLIN': {'how'}, 'CANCUN': {'im'}}, 'MOSCOWtwo': {'AMSTERDAM': {'cars'}}, 'BERLINthree': {'AMSTERDAM': {'are'}}, 'AMSTERDAMthree': {'MILAN': {'are'}}, 'MILANthree': {'PARIS': {'the'}}, 'CANCUNthree': {'LONDON': {'john'}}, 'AMSTERDAMfour': {'MILAN': {'you'}}, 'MILANfour': {'LONDON': {'fast'}}, 'PARISfour': {'CANCUN': {'bank'}}, 'LONDONfour': {'FLORENCE': {'smith'}}}
def get_vals(s, c = [], t=[]):
   if (k:=next(filter(lambda x:x not in t, hints), None)):
      for a, [b] in d.get(f'{s}{k}', {}).items():
         yield from get_vals(a, c=c+[b], t=t+[k])
   else:
      yield c+[s]

print(list(get_vals('ROME')))

输出：

[['hello', 'how', 'are', 'you', 'MILAN'], 
 ['hello', 'im', 'john', 'smith', 'FLORENCE'], 
 ['money', 'in', 'the', 'bank', 'CANCUN'], 
 ['racing', 'cars', 'are', 'fast', 'LONDON']]

从字典构建字符串的递归函数

Recursive function to build a string from dictionaries

python

dictionary

recursion

binary-search-tree