如何将递归函数重写为循环？

Question

这个Stack Overflow的讨论说，每个递归函数都可以用循环来写。

哪些递归函数不能用循环重写？

这个说法很有道理。不过，我不太确定怎么把下面这个递归函数写成循环，因为它在递归之前和递归之后都有一些逻辑。

显然，解决方案不能使用goto语句。代码在这里：

def gen_perms(lst, k, m):

    if k == m:
        all_perms.append(list(lst))
    else:
        for i in xrange(k, m+1):

            #swap char
            tmp = lst[k]
            lst[k] = lst[i]
            lst[i] = tmp

            gen_perms(lst, k+1, m)

            #swap char
            tmp = lst[k]
            lst[k] = lst[i]
            lst[i] = tmp

调用这个函数的方式是这样的：

all_perms = []
gen_perm([1, 2, 3], 0, 2)

它会生成列表1,2,3的所有排列组合。

Answer 1

假设你想找出数组 [1, 2, 3, 4] 的所有排列组合。这个数组一共有24种排列（因为4的阶乘是24），我们可以把它们编号从0到23。我们想要找到第N个排列，但不想用递归的方法。

如果我们把这些排列按数字大小排序，那么：

• 编号为0到5的排列以1开头
• 编号为6到11的排列以2开头
• 编号为12到17的排列以3开头
• 编号为18到23的排列以4开头

所以，我们可以通过把N除以6（也就是3的阶乘），然后向上取整，来找到排列N的第一个数字。

那么，接下来我们怎么找第二个数字呢？看看编号为0到5的排列的第二个数字：

• 编号为0和1的排列的第二个数字是2。
• 编号为2和3的排列的第二个数字是3。
• 编号为4和5的排列的第二个数字是4。

对于编号为6到11的排列，我们也能看到类似的情况：

• 编号为6和7的排列的第二个数字是1。
• 编号为8和9的排列的第二个数字是3。
• 编号为10和11的排列的第二个数字是4。

一般来说，先把之前的结果对6取余，然后再除以2（也就是2的阶乘），再向上取整。这样你会得到1、2或3，而第二个数字就是在去掉第一个数字后，列表中剩下的第1、2或3个数字。

你可以继续这样进行下去。下面是实现这个过程的一些代码：

from math import factorial

def gen_perms(lst):
    all_perms = []

    # Find the number of permutations.
    num_perms = factorial(len(lst))

    for i in range(num_perms):
        # Generate the ith permutation.
        perm = []
        remainder = i

        # Clone the list so we can remove items from it as we
        # add them to our permutation.
        items = lst[:]

        # Pick out each item in turn.
        for j in range(len(lst) - 1):
            # Divide the remainder at the previous step by the
            # next factorial down, to get the item number.
            divisor = factorial(len(lst) - j - 1)
            item_num = remainder / divisor

            # Add the item to the permutation, and remove it
            # from the list of available items.
            perm.append(items[item_num])
            items.remove(items[item_num])

            # Take the remainder for the next step.
            remainder = remainder % divisor

        # Only one item left - add it to the permutation.
        perm.append(items[0])

        # Add the permutation to the list.
        all_perms.append(perm)

    return all_perms

Answer 2

在Python中，做排列的最简单、最优雅的方法是使用：

>>> from itertools import permutations
>>> permutations([1,2,3])
>>> list(permutations([1,2,3]))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

Answer 3

我对Python的语法不是很熟悉，不过下面这段用'C'写的代码应该不难翻译成Python，前提是Python也支持嵌套的for循环。

int list[3]={1,2,3};
int i,j,k;

for(i=0;i < SIZE;i++)
for(j=0;j < SIZE;j++)
for(k=0;k < SIZE;k++)
if(i!=j && j!=k && i!=k)
printf("%d%d%d\n",list[i],list[j],list[k]);