在python中递归排列

Question

如何格式化此函数以使其递归工作？如果可能的话，我想深入多个层次，而不仅仅是5。

排列是一个具有不同排列的列表，这些单独的排列也可以有排列等。我想根据我在get_permutations中进行的一些计算对它们进行排序，并返回新的排列顺序。查看它的一个好方法可能是一个列表的大列表。首先，我想改变第一级的顺序，比深一步等等。但最终我返回的字符串是基于这些排列，而不是排列本身(如果这很重要的话)，res1…res5是字符串。我还不够聪明，不能让它递归地工作，尽管我知道这应该是可能的。。。有什么想法吗？

permutations, res1 = get_permutations(str, 1)
for p2 in permutations:
permutations_2, res2 = get_permutations(p2,2)
for p3 in permutations_2:
permutations_3, res3 = get_permutations(p3,3)
for p4 in permutations_3:
permutations_4, res4 = get_permutations(p4, 4)
for p5 in permutations_4:
permutations_5, res5 = get_permutations(p5,5)
res4 += res5
res3 += res4    
res2 += res3    
res1 += res2
return res1

EDIT：返回单个(最佳)排列。这就是结果。因此，并不是答案中提到的可能排列的列表。例如，如果我们有一个列表列表列表，如果首先根据所有子信息对列表进行排序，然后根据之前的排序和所有子信息将多个列表列表排序，然后基于之前的2个排序对列表列表列表进行排序。

Answer 1

一个递归生成器函数，它按照原始字符串的预期顺序生成排列：

def get_permutations(a):
if len(a) <= 1:
yield a
else:
for i in xrange(len(a)):
for p in get_permutations(a[:i]+a[i+1:]):
yield ''.join([a[i]])+p
>>> a = '123'
>>> list(get_permutations(a))
['123', '132', '213', '231', '312', '321']

这里的递归原理：

1. 基本情况：长度为(0, 1)的字符串只有一个排列：它们自己。

2. 递归：对于字符串中的每个字母，将其移除，并将其置于字符串余数的每个排列之前。

Answer 2

下面的一个例子，这个方法通过以递归方式嵌套循环来重复次数。然后，我们累积子解决方案的结果，并将其附加到结果列表中：

result = []
def permutations(alphabet, repeat, total = ''):
if repeat >= 1:
for i in alphabet:
# Add the subsolutions.     
permutations(alphabet, repeat - 1, total + i)  
else:
result.append(total)
return result

样本输出：

permutations('ab', 3) ->
$ ['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb']
permutations('ab', 3) ->
$ ['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa',
'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab', 
'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']
permutations('ab', 1) ->
$ ['a', 'b']

来源：我之前的回答