在for循環中遞歸運行for循環（python）

Question

我是python的新手，並試圖用它來解決電視節目倒計時中的數字遊戲。 （rules for those unfamiliar）。我用Google搜索了一下，結果發現this has been done before - 但我沒有正確理解代碼，然後想到爲什麼不直接給自己一個人去。我搜索了，還有其他人在尋找遞歸解決方案，但我無法讓他們爲我的例子工作（道歉，畢竟我對此很新）。

我想要做的是獲取一個數字列表，然後循環通過應用操作對他們和取代那對輸出。這將重複遞歸，直到我們找到我們正在查找的數字，或數字列表減少到1。

我的函數「single_move_generator」是一個生成元組的形式（（a，b，操作），答案，剩下的號碼可以使用）。我想把這個元組的最後部分作爲新列表反饋到函數中，但也要跟蹤第一部分，因爲它是我們如何實現答案的'歷史'。目前，我有以下幾點：

target = 155 
numbers_to_use = [6, 25, 3, 2] 
for a in single_move_generator(numbers): 
    if a[1] == target: 
     print(a[0]) 
    for b in single_move_generator(a[2]): 
     if b[1] == target: 
       print(a[0],b[0]) 
       quit() 
     for c in single_move_generator(b[2]): 
       if c[1] == target: 
        print(a[0],b[0],c[0]) 
        quit() 

生產：

(25, 6, 'add') (3, 2, 'add') (31, 5, 'multiply') 

但我希望能夠給它編號更大的列表，並有它只是繼續下去，直到達到列表大小爲一。我懷疑我需要一個while循環 - 但這種嘗試不起作用。它沒有找到目標或跟蹤移動的歷史。

numbers_available = numbers 
while len(numbers_available) >1 and target not in numbers_available: 

    for a in single_move_generator(numbers_available): 
     if a[1] == target: 
      print("Target Found", a)   
      break 

    numbers_available = a[2] 

numbers_available = a[2] 

我覺得必須有這樣做是很整齊，比我做過的Python的方式 - 任何暗示將不勝感激。謝謝！

Answer 1

根據你貼什麼，這應該爲你工作：

def solve(numbers, target): 
    for op, res, nums in single_move_generator(numbers): 
    if res == target: 
     return [op] 
    ops = solve(nums, target) 
    if ops: 
     return [op] + ops 

print(*solve(numbers_to_use, target)) 

應該等同於嵌套的for循環您發佈。

遞歸的底部是res == target。默認情況下，Python函數返回None，所以如果遞歸調用solve返回真值，則它必須已經達到目標。如果它是遞歸的底部，則ops將包含最後的操作。然後將它附加到啓動遞歸調用並返回到上一級的操作。所以該函數將返回頂層的所有操作。

Answer 2

根據你使用元組的想法(i, j, operation)，我寫了以下內容。這是一個遞歸解決方案，因爲主函數會自行調用回來。

from itertools import combinations, product 

def check_operation(i, j, operation): 
    """ 
    Check whether 'i operation j' is permitted. 
    """ 
    if operation == '/' and j == 0: 
     return False 
    elif operation == '/' and i%j != 0: 
     return False 
    # if not playing with negative values 
    #elif operation == '-' and i-j < 0: 
    # return False 
    else: 
     return True 

def countdown(target, numbers, trackback): 
    if target in numbers: 
     print trackback 
    for possibility in product(combinations(numbers,2), ['+', '*', '/', '-']): 
     new_numbers = [k for k in numbers] # copy list, use list.copy in python 3 
     i, j = possibility[0][0], possibility[0][1] 
     operation = possibility[1] 
     new_numbers.remove(i) 
     new_numbers.remove(j) 
     if not check_operation(i, j, operation): 
      continue 
     new_numbers.append(eval('%i%s%i' % (i, operation, j))) 
     countdown(target, new_numbers, trackback+[possibility]) 

countdown(155, [6, 25, 3, 2], []) 

它只適用於存在解決方案的情況，因爲它不打算儘可能接近解決方案。但是，它將返回所有解決方案，而不僅僅是一個。