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 条评论
登录 后参与评论

相关文章

来自专栏Hongten

java中的移位运算符:<<,>>,>>>总结

value >>> num     --   num 指定要移位值value 移动的位数。

23250
来自专栏Golang语言社区

go语言json操作指南

1、Go语言的JSON 库   Go语言自带的JSON转换库为 encoding/json 1.1)其中把对象转换为JSON的方法(函数)为 json.Mar...

379120
来自专栏用户2442861的专栏

JavaScript 正则表达式上——基本语法

JavaScript种正则表达式有两种定义方式,定义一个匹配类似 <%XXX%> 的字符串

7210
来自专栏机器学习入门

挑战程序竞赛系列(89):3.6平面扫描(3)

挑战程序竞赛系列(89):3.6平面扫描(3) 传送门:POJ 3292: Rectilinear polygon 题意参考hankcs: http://w...

21250
来自专栏Golang语言社区

go语言json操作指南

1、Go语言的JSON 库   Go语言自带的JSON转换库为 encoding/json 1.1)其中把对象转换为JSON的方法(函数)为 json.Mar...

44680
来自专栏Golang语言社区

go语言基本类型

这篇文章主要介绍了GO语言基本类型,较为详细的分析了整形、浮点型、字符串、指针等类型的具体用法,是深入学习GO语言所必须掌握的重要基础,需要的朋友可以参考下 ...

32960
来自专栏racaljk

Leetcode 413. Arithmetic Slice 算术序列切片(动态规划,暴力)

16320
来自专栏Golang语言社区

【Go 语言社区】Golang 动态实例化结构体

但这里有一个限制:这个 map 仅仅可以用原型是“func()”的没有输入参数或返回值的函数。 如果想要用这个方法实现调用不同函数原型的函数,需要用到 inte...

430120
来自专栏java系列博客

ORACLE

24840
来自专栏Jackson0714

C# 正则表达式

12320

扫码关注云+社区

领取腾讯云代金券