のpython再帰関数を記述しようとすると

Question

私は、次のリストがあります：3の各グループから1つの文字を選択し、すべての可能な組み合わせ/順列を返します。再帰関数を記述するための最良の方法は何

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

を：

例出力は次のように

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時間も過ごしていましたが、まだ近くにはありません。どんな助けもありがとう！

Answer 1

が空のリストについては、あなたの結果は空のリストであることを考慮して、すなわち任意の非空のリストについては

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では、これは（やや非効率的で冗長ですが、彼は）アルゴリズム：

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

Answer 2

のようにこの関数を呼び出します。効率とそれが生成する値の順序のためにコードを調整する必要があるかもしれません。再帰関数は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()