python 利用递归实现全排列

使用递归实现全排列。123实现全排列! 法1:

上面定义了两个列表,一个列表存的是需要全排列的数据,另一个列表是当做栈来用的,可以把这个递归想成一棵树,在最顶端是包含所有值得列表,之后从这个列表中循环拿掉一个值,到了第二层,这时候栈里面存放的就是拿出来的那个数据,这一层的一个值里面就少了刚刚拿掉的值,一直到最后这个列表为空的时候,栈里面存的就是这个排列的结果,

#!/usr/bin/env python
# encoding:utf-8


def perm(list,stack):
    if not list:
        print(stack)  # 到树的最后,输出结果
    else:  # 没有到树的叶子节点的时候,使用递归继续往下找。
        for i in range(len(list)):
            stack.append(list[i])
            del list[i]
            perm(list,stack)
            list.insert(i,stack.pop())

list=[1,2,3]
stack=[]
perm(list,stack)

同时在python中有一个模块叫做itertools,使用这个模块能够快速的求解排列组合问题 OK,这样理解起来是不是容易多了,这样也能够解释为什么递归其实就是一棵树了。。。当然,也可以使用栈来代替递归实现,不过。。。目前还没实现。区别差不多就是树的递归遍历和非递归遍历的区别吧。 法二、 排列:从n个元素中任取m个元素,并按照一定的顺序进行排列,称为排列; 全排列:当n==m时,称为全排列;

比如:集合{ 1,2,3}的全排列为: { 1 2 3} { 1 3 2 } { 2 1 3 } { 2 3 1 } { 3 2 1 } { 3 1 2 }

递归思想: 取出数组中第一个元素放到最后,即a[1]与a[n]交换,然后递归求a[n-1]的全排列

1)如果数组只有一个元素n=1,a={1} 则全排列就是{1} 2)如果数组有两个元素n=2,a={1,2} 则全排列是: {2,1}–a[1]与a[2]交换。交换后求a[2-1]={2}的全排列,归结到1) {1,2}–a[2]与a[2]交换。交换后求a[2-1]={1}的全排列,归结到1) 3)如果数组有三个元素n=3,a={1,2,3} 则全排列是 {{2,3},1}–a[1]与a[3]交换。后求a[3-1]={2,3}的全排列,归结到2) {{1,3},2)–a[2]与a[3]交换。后求a[3-1]={1,3}的全排列,归结到2) {{1,2},3)–a[3]与a[3]交换。后求a[3-1]={1,2}的全排列,归结到2) … 依此类推。 利用python实现全排列的具体代码perm.py如下:

OUNT=0  
def perm(n,begin,end):  
    global COUNT  
    if begin>=end:  
        print n  
        COUNT +=1  
    else:  
        i=begin  
        for num in range(begin,end):  
            n[num],n[i]=n[i],n[num]  
            perm(n,begin+1,end)  
            n[num],n[i]=n[i],n[num]  

n=[1,2,3,4]  
perm(n,0,len(n))  
print COUNT  

[参考连接]【1】 【2】

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏生信小驿站

Python从零开始第三章数据处理与分析python中的dplyr(4)目录

可以使用separate(column,into,sep =“[\ W _] +”,remove = True,convert = False,extra ='...

12320
来自专栏Python爱好者

LeetCode-1 两数之和(python3)

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

24020
来自专栏生信小驿站

Python从零开始第三章数据处理与分析python中的dplyr(3)目录

===============================================

10230
来自专栏python入门学习

Python到底能做什么?它的优点在哪?

Python今天是排名前3的最受欢迎和增长最快的编程语言之一。它是一种多用途,高级别,面向对象,交互式,解释型和对用户非常友好的编程语言。

17730
来自专栏py+selenium

python+selenium 批量执行时出现随机报错问题【已解决】

出现场景:用discover方法批量执行py文件,出现随机性的报错(有时a.py报错,有时b.py报错...),共同特点:均是打开新窗口后,切换最新窗口,但定位...

16540
来自专栏月色的自留地

从零开始学习PYTHON3讲义(十三)记事本的升级版:网络记事本

网络编程的火热和重要性这里就不多说了,我们直接来看看Python在互联网编程方面的表现。

20930
来自专栏生信小驿站

Python从零开始第三章数据处理与分析①python中的dplyr(2)目录

===============================================

11410
来自专栏weixuqin 的专栏

leecode刷题(5)-- 只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

13210
来自专栏月色的自留地

从零开始学习PYTHON3讲义(十一)计算器升级啦

(内容需要,本讲中再次使用了大量在线公式,如果因为转帖网站不支持公式无法显示的情况,欢迎访问原始博客。)

19030
来自专栏生信小驿站

Python从零开始第三章数据处理与分析①python中的dplyr(1)

我经常使用R的dplyr软件包进行探索性数据分析和数据处理。 dplyr除了提供一组可用于解决最常见数据操作问题的一致函数外,dplyr还允许用户使用管道函数编...

12940

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励