前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python|“套娃”算法-递归算法解决全排列

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

作者头像
算法与编程之美
发布2020-04-07 17:07:14
1.3K0
发布2020-04-07 17:07:14
举报
文章被收录于专栏:算法与编程之美

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

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时);

代码语言:javascript
复制
def full_array(List):

    if len(List)==1:

        return [List]

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

代码语言:javascript
复制
for i in range(len(List)):

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

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

代码语言:javascript
复制
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)   

完整代码:

代码语言:javascript
复制
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 总结

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-04-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法与编程之美 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档