Python|“套娃”算法-递归算法解决全排列

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

1 什么是递归？

什么是递归？晦涩难懂而又有学术气息的解释网上到处都有。今天就为大家带来一个‘船新版本’。

相信不少人在各种社交APP上都见过‘禁止套娃’的评论，而什么是套娃呢？套娃其实是俄罗斯是特产的木制玩具，一般由多个相同图案的空心木娃娃一个套一个的组成，一般在六个以上。由此 ‘套娃’这个梗的意思也就清晰了：在各种社交网站或视频下方评论区跟人争论时使用重复类似的语言。

图1 递归

有个笑话是这样的：

记者：你放羊为了什么?

放羊娃：赚钱

记者：你赚钱为了什么?

放羊娃：娶媳妇

记者：你娶媳妇为了什么?

放羊娃：生娃

记者：生了娃干什么

放羊娃：放羊。

看了上面的例子，再结合递归的‘调用函数本身’，就理解了递归的含义。通俗讲就是 ‘为所欲为’ 之 ‘为所欲为’ 之 ‘为所欲为’ ……

2 递归全排列

在明白了递归含义后，就来做一个小小的实践：用代码输出[1,2,3,4]数列的全部排列情况（全排列）

思路一

按照数学题思路：

第一个数有4种情况（1，2，3，4），第二个数有3种（除开第一个数），第三个数有2种（除开第一个数和第二个数），第四个数有1种（剩下的数）

因此套用4层循环就可以解决。但是如果不知道列表的长度，此方法就不成立。

思路二

既然理解了递归，就用递归的方法。可以认为是以n1（依次遍历列表）为头部，加上[n2, n3,n4 ,……nn]的全排列，而[n2,n3 ,n4 ,……nn]的全排列可以看成以为头部，加上[n3,n4 ,……nn]的全排列……剩下的就是‘套娃’了，一直套到列表长度为1。

步骤

1.先定义full_array函数，并设置递归结束条件（即列表长度为1时）；

def full_array(List):

    if len(List)==1:

        return [List]

2.遍历列表作为头部，并生成下一个 ‘去头部的列表’ ；

for i in range(len(List)):

    array=List[:i]+List[i+1:]

3.对递归后的‘去头部列表’遍历，并与前面所删除的部分相加。

for i in range(len(List)):

    array=List[:i]+List[i+1:]

    for ii in full_array(array):

         Mid=[List[i]]+ii

         Result.append(Mid)   

完整代码：

def full_array(List):

    Result=[]

    if len(List)==1:

        return [List]

    else:

        for i in range(len(List)):

            array=List[:i]+List[i+1:]

            for ii in full_array(array):

                Mid=[List[i]]+ii

                Result.append(Mid)

    return Result        

print(full_array([1,2,3]))

3 总结

递归就是‘套娃’，一层套一层，但必须设置一个结束条件，就像‘套娃’一定会打开最后一个，递归也必须有最后一层，防止无线递归。而一般也规定了递归最大深度，一旦超过栈就会溢出。递归对不同的问题，使用的位置也不同，因此应该学会递归的思想，而不是狭隘地认为自己仅会阶乘运算，就算得上掌握了递归算法。