试图写一个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递归函数

回答

相关问题