試圖寫一個Python遞歸函數

我有以下列表：試圖寫一個Python遞歸函數

list = ['ABC', 'DEF', 'GHI']

什麼是寫一個遞歸函數，將挑選從每組三個一個字母，並返回所有可能的組合/排列的最佳方式：

Eg輸出如下：

A，AD，ADG，ADH，ADI，AEG，AEH，AEI，AFG，AFH，AFI

B，BD，BDG，BDH，BDI，BEG，BEH，BEI ，BFG，BFH，BFI

C，CD，CDG，CDH，CDI，CEG，CEH，CEI，CFG，CFH，CFI

d，DG，DGA，DGB，DGC，DHA，...等等...

我正在學習遞歸函數。到目前爲止，我已經連續花了7個小時來解決這個問題，而且還沒有完成。任何幫助表示讚賞！

來源

2016-04-06 Peter

請添加你試過的東西。 –

你不需要爲此遞歸 –

假設你已經給出了一個函數foo（）來解決這個問題的大小爲2的團體，你如何使用它？ – Elazar

認爲，爲空列表，你的結果是空列表（這是你的「基本情況」），即

f([]) == ""

對於任何非空列表，你把第一個列表中的每個字符元素（列表中的「頭」），並在前面加上通過遞歸地施加你的函數，其餘的名單（即「尾」）返回的每個字符串（這是你的「遞歸的情況下」）：

f(['ABC']) 
    == 'A' + f([]), 'B' + f([]), 'C' + f([]) 
    == 'A' + '', 'B' + '', 'C' + '' 
    == 'A', 'B', 'C' 

f(['ABC', DEF']) 
    == 'A' + f(['DEF']), 'B' + f(['DEF']), 'C' + f(['DEF']) 
    == 'A' + 'D' + f([]), 'A' + 'E' + f([]), 'A' + 'F' + f([]), 'B' + 'D' + f([]) ... 
    == 'AD', 'AE', 'AF', 'BD', 'BE', 'BF', 'CD', 'CE', 'CF'

在Python中，可以表達爲（效率低下和冗長，但重點在於顯示t他的算法）：

def f(xs): 
    if not xs: 
     yield '' 
    else: 
     head = xs[0] 
     tail = xs[1:] 

     for char in head: 
      yield char 
      for s in f(tail): 
       yield char + s

調用像

print list(f(['ABC', 'DEF', 'GHI']))

打印

['A', 'AD', 'ADG', 'ADG', 'ADH', 'ADH', 'ADI', 'ADI', 'AE', 'AEG', 'AEG', 'AEH', 'AEH', 'AEI', 'AEI', 'AF', 'AFG', 'AFG', 'AFH', 'AFH', 'AFI', 'AFI', 'B', 'BD', 'BDG', 'BDG', 'BDH', 'BDH', 'BDI', 'BDI', 'BE', 'BEG', 'BEG', 'BEH', 'BEH', 'BEI', 'BEI', 'BF', 'BFG', 'BFG', 'BFH', 'BFH', 'BFI', 'BFI', 'C', 'CD', 'CDG', 'CDG', 'CDH', 'CDH', 'CDI', 'CDI', 'CE', 'CEG', 'CEG', 'CEH', 'CEH', 'CEI', 'CEI', 'CF', 'CFG', 'CFG', 'CFH', 'CFH', 'CFI', 'CFI']

來源

2016-04-06 15:32:52

此功能下面的程序應該是接近你問什麼。您可能需要調整代碼以提高效率和對其生成的值進行排序。請注意，遞歸函數嵌入在possibilities之內，並根據需要最終在各級調用其自身。

def main(): 
    for value in possibilities('ABC', 'DEF', 'GHI'): 
     print(value) 


def possibilities(*args): 
    if len(args) < 2: 
     raise ValueError('at least two arguments must be given') 
    if any(not isinstance(arg, str) for arg in args): 
     raise TypeError('all arguments must be strings') 
    if any(not arg for arg in args): 
     raise ValueError('strings must have at least one character') 
    matrix = [[''] + list(arg) for arg in args] 

    def recursive_function(array): 
     for index in range(len(array)): 
      row = array.pop(index) 
      if array: 
       for column in row: 
        for next_item in recursive_function(array): 
         yield column + next_item 
      else: 
       yield from row 
      array.insert(index, row) 

    def unique(iterator): 
     values = {''} 
     for value in iterator: 
      if value not in values: 
       values.add(value) 
       yield value 
    return sorted(unique(recursive_function(matrix))) 


if __name__ == '__main__': 
    main()

來源

2016-04-06 15:33:47

試圖寫一個Python遞歸函數

回答

相關問題