如何编写大量嵌套'for'循环（递归）

Question

word = "word" 

# Splitting word into its characters 
newword = [] 
for char in word: 
    newword.append(char) 

print newword 


#getting all permutations 
test= [] 
for i in newword: 
    for j in newword: 
     if i != j: 
      for k in newword: 
       if j != k and i!= k: 
        for l in newword: 
         if i != l and j != l and k != l: 
          test.append(i+j+k+l) 

print test 
print type(test) 
print len(test) 

这4个嵌套循环很适合'单词'，因为它正好有4个字母。 如果我想为任何给定单词中的字母尽可能多的'for'循环，我该怎么做？ 任何不错的窍门？

Answer 1

这是您试图解决的一般递归问题。 itertools已经包含了几乎所有您可能需要的实现的功能。然而，如果你想了解一些东西，这是一种做法。我将排列一个数字列表。在这种情况下，我会找到的排列：

[0,1,2, ... ,N-1] 

注意，一旦你有一个以上的排列，你可以简单地使用这些作为指标用于置换任何东西。那么这样做的一般方法是什么？

让我们先看看特定情况下的结果。例如[0,1,2,3]。我们正在寻找的结果是列出的清单：

[[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], 
[0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], 
[1, 3, 0, 2], [1, 3, 2, 0], [2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3], 
[2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0], [3, 0, 1, 2], [3, 0, 2, 1], 
[3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]] 

的想法是写一个函数，它列出了一个清单，并增量它。考虑简单的功能：

def permNums(inp, N=4): 
    newInp = [] 
    for i in inp: 
     for j in range(N): 
      if j not in i: newInp.append(i+[j]) 
    return newInp 

现在用列表的一个空表执行此功能可按...

In [22]: permNums([[]]) 
Out[22]: [[0], [1], [2], [3]] 

当你与它的输出再次运行它，会发生什么？

In [23]: permNums(_) 
Out[23]: 
[[0, 1], 
[0, 2], 
[0, 3], 
[1, 0], 
[1, 2], 
[1, 3], 
[2, 0], 
[2, 1], 
[2, 3], 
[3, 0], 
[3, 1], 
[3, 2]] 

并重复一遍？

In [24]: permNums(_) 
Out[24]: 
[[0, 1, 2], 
[0, 1, 3], 
[0, 2, 1], 
[0, 2, 3], 
[0, 3, 1], 
[0, 3, 2], 
[1, 0, 2], 
[1, 0, 3], 
[1, 2, 0], 
[1, 2, 3], 
[1, 3, 0], 
[1, 3, 2], 
[2, 0, 1], 
[2, 0, 3], 
[2, 1, 0], 
[2, 1, 3], 
[2, 3, 0], 
[2, 3, 1], 
[3, 0, 1], 
[3, 0, 2], 
[3, 1, 0], 
[3, 1, 2], 
[3, 2, 0], 
[3, 2, 1]] 

再来一次，你会得到你想要的结果。

现在你可以考虑简单的实现：

result = [[]] 
for i in range(N): result = permNums(_) 

这将解决您的问题（你只需要索引映射到您的字符串，并加入结果）。但是，这不是经典的递归。对于递归，您需要执行另外两个步骤。

1. 调用它自己内部的功能
2. 图出来时，这个主叫本身业务将停止...

内本身调用函数是简单的。只需更换

return newInp 

与

return permNums(newInp, N) 

，因为这是你手动做IPython的控制台上正是这一步并不奇怪。但是，您需要在某个时候停下来。在这种特殊情况下，停止标准应该很简单。如果其中一个内部列表== N中的元素数量停止。

所以修改后的方案有两个简单的加法：

def permNums(inp, N=4): 

    if len(inp[0]) == N: return inp # stopping criterion 

    newInp = [] 
    for i in inp: 
     for j in range(N): 
      if j not in i: newInp.append(i+[j]) 

    return permNums(newInp, N) # keep calling itself 

print permNums([[]])  

希望这有助于...

Answer 2

In [10]: import itertools 

In [11]: word = "word" 

In [12]: test = [''.join(perm) for perm in itertools.permutations(word)] 

In [13]: test 
Out[13]: 
['word', 
'wodr', 
'wrod', 
'wrdo', 
'wdor', 
'wdro', 
'owrd', 
'owdr', 
'orwd', 
'ordw', 
'odwr', 
'odrw', 
'rwod', 
'rwdo', 
'rowd', 
'rodw', 
'rdwo', 
'rdow', 
'dwor', 
'dwro', 
'dowr', 
'dorw', 
'drwo', 
'drow']