python标准算法实现数组全排列的方法

python标准算法实现数组全排列的方法（精选5篇）

篇1：python标准算法实现数组全排列的方法

作者：八大山人 字体：[增加 减小] 类型：

这篇文章主要介绍了python标准算法实现数组全排列的方法,实例分析了全排列的原理与Python实现技巧,需要的朋友可以参考下

本文实例讲述了python标准算法实现数组全排列的方法，代码来自国外网站，分享给大家供大家参考。具体分析如下：

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

def Mideng(li): if(type(li)!=list): return if(len(li)==1): return [li] result=[] for i in range(0,len(li[:])): bak=li[:] head=bak.pop(i) #head of the recursive-produced value for j in Mideng(bak):j.insert(0,head)result.append(j) return resultdef MM(n): if(type(n)!=int or n<2): return return Mideng(list(range(1,n)))

调用方法：

MM(6)

希望本文所述对大家的Python程序设计有所帮助，

篇2：python标准算法实现数组全排列的方法

这篇文章主要介绍了python常规方法实现数组的全排列,实例分析了全排列的概念及Python常规实现技巧,需要的朋友可以参考下

本文实例讲述了常规方法实现python数组的全排列操作，分享给大家供大家参考。具体分析如下：

全排列解释：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

def perm(l): if(len(l)<=1): return [l] r=[] for i in range(len(l)): s=l[:i]+l[i+1:] p=perm(s) for x in p:r.append(l[i:i+1]+x) return r

调用方法：

if __name__==‘__main__‘: “”“ default param is list(1,2,3,4,5) ”“” l=[]; if(len(sys.argv)<=1): “”“input=[‘%d‘ %(i) for i in xrange(1,6)]”“” l=list((1,2,3,4,5)) else:#input param looks like “2,3,4,5,6”,no legal checks here. input=str(sys.argv[1]) l=input.split(“,”) for i in xrange(len(l)): l[i] = int(l[i]) print perm(l)

篇3：全排列的递归算法实现

从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列[1]。

某全排序问题:将一个字符组全排序。输入文件(Sortwide.in)包含一个长度小于8的字符串,该字符串由数字1~9组成,字符不会重复出现;要求按数字从小到大的顺序输出该字符组的全排序,并将结果保存在文件中(Sortwide.out)。

2 递归算法

2.1 基本概念

直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。使用递归技术可以使函数的定义和算法的描述简洁且易于理解。有些数据结构如二叉树,由于其本身固有的递归特性,特别适合用递归的形式来描述。另外有些问题,虽然本身没有明显的递归结构,但用递归技术来求解使设计出的算法简洁易懂且易于分析[1]。

2.2 过程实现

递归算法包括“递推”和“回归”2部分[1]。

2.2.1 递推

递推就是为得到问题的解,将它推到比原问题简单的问题的求解。递推应有终止之时,即有所谓的“终止条件”,在此条件下,问题的解是明确的;“简单问题”表示离递推终止条件更为接近的问题。

2.2.2 回归

回归指当“简单问题”得到解后,回归到原问题的解上来。

3 C语言递归编程求解全排列

C语言是国际上广泛流行的功能强大的高级程序设计语言,语言简洁、紧凑,使用方便、灵活[2]。采用C语言可以很方便地解决全排列问题。

3.1 数据结构

数据结构[3]是计算机存储、组织数据的方式。精心选择的数据结构可以带来更高的运行或者存储效率的算法。一个数据结构是由数据元素依据某种逻辑联系组织起来的。在不同的程序设计语言中,选择不同的数据结构,可以得到高效的题解。

在C语言中主要构造一维数组char list[],用以存放排列序列,并将其设置为全局变量。为统计总共排列个数,设置一个全局变量,初始值为0,即int n=0,(如果字符达到8个,则需设置为long n=0);设置一个全局变量len,用以记录字符长度,初始值为0,即int len=0。

3.2 全排列的递归求解思想和函数void perm(int k,int m)

3.2.1 递归求解思想

设R={r0,r1,…,rn-1}是要进行排列的n个元素,观察当n=1,n=2,n=3时的全排列。

将n=3时的全排列分成3组,可得第1组是由r1与r2的全排列加上前缀r0得到的,第2组是由r0与r2的全排列加上前缀r1得到的,依此类推可知,3个元素的全排列问题可转化成求2个元素的全排列问题;从而n个元素的全排列问题可转化成求n-1个元素的全排列问题,由此找到递归关系。引入记号perm(R)表示集合R的全排列,Ri=R-{ri},{ri}perm(Ri)表示集合除ri元素外的所有元素的全排列前加上前缀ri后得到的排列。则R的全排列递归定义为:

3.2.2 构造递归函数

函数Perm(Object[]list,int k,int m)[4]是求将list的第0~k-1个元素作为前缀、第k~m-1个元素进行全排列得到的全排列,如果k为0,且m为n,就可以求得一个数组中所有元素的全排列。全排列的递归构造过程就是对全排列树的深度优先搜索过程,其递归函数中主要过程为当k

事实上,当list作为全局变量出现时,swap(list,k,i)可以写成swap(k,i),而不用作为参数传递;其交换函数也就为常规地将相应的2个值交换;

该递归算法能够求解出全排列,但不能够满足按数字从小到大的顺序输出要求;和文献4相比,改进递归算法思想:修改递归中的交换操作,具体交换见下文描述的函数swap1(k,i)和swap2(k,i)。例如序列1、2、3、4、5;当k=1,i=3时;原递归思想操作为,交换1、3位置的值得到1、4、3、2、5,然后递归调用,再交换1、3位置回到原序列1、2、3、4、5,其交换如图1所示。改进的算法思想为交换1、3位置时不再是单纯地交换1、3位置,而是将1、2位置的值移到2、3位置,3位置的值交换到1位置,得到1、4、2、3、5,然后递归调用,再交换回到原序列1、2、3、4、5。2次交换分别如图2、图3所示。

3.2.3 两个重要的交换函数

void swap2(int a,int b)类似于swap1,不再完整给出。

3.2.4 完整递归函数

3.3 读取待全排序的字符组函数int in_file_qpl()

本函数的sort()函数用来完成将初始输入的字符序列list从小到大排序,可以采用直接选择法或者冒泡法编写。

3.4 完整程序

上文中已经完整给出的sort()、in_file_qpl()、swap1()、swap2()以及perm()函数,不再详细描述,函数体部分均使用{…}替代。

4 仿真结果

使用笔记本电脑IBMR50e,CPU主频1.6 GHz,512M内存,Windows XP操作系统,Turboc 2.0环境运行。Sortwide.in文件中内容为15342,运行本程序,可以迅速得到解文件Sortwide out,其中包含了120个从小到大排序的全排列结果,耗时0.4秒;当内容为1376452时,排列7个字符时,本程序虽然将结果既输出到屏幕同时又输出到文件,耗时也仅为2.8秒。

5 结语

对全排列组合的递归求解不仅能够体现了递归算法的优点,而且给出了利用递归算法解决类似问题的一个思路;掌握递归思想,巧妙地利用递归算法可以解决许多数学难题。

摘要：递归算法的设计与实现是非常重要的内容,全排列是组合数学中最常见的问题。提出了基于递归算法并通过C语言编程实现了计算机解题,实例数据表明程序非常高效。

关键词：递归,全排列,全排列递归算法

参考文献

[1]王晓东.算法设计与分析[M].北京:清华大学出版社,2003,1:19.

[2]谭浩强.C程序设计[M].3版.北京:清华大学出版社,2005,1:3,140-143,171-177,342.

[3]严蔚敏,吴伟民.数据结构[M].2版.北京:清华大学出版社,1993,6:93-95,43-45,220-221.

篇4：python标准算法实现数组全排列的方法

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列，

这段代码用到了yield方法，全排列速度加倍

def perm(arr, pos = 0): if pos == len(arr): yield arr for i in range(pos, len(arr)): arr[pos], arr[i] = arr[i], arr[pos] for _ in perm(arr, pos + 1): yield _ arr[pos], arr[i] = arr[i], arr[pos]for i in perm([1,2,3,4]): print i

篇5：python标准算法实现数组全排列的方法

这篇文章主要介绍了python实现数组插入新元素的方法,涉及Python中insert方法的相关使用技巧,需要的朋友可以参考下

本文实例讲述了python实现数组插入新元素的方法，分享给大家供大家参考。具体如下：

li=[‘a‘, ‘b‘] li.insert(0,“c”)

输出为:[‘c‘, ‘a‘, ‘b‘]

li=[‘a‘, ‘b‘]li.insert(-1,“c”)

输出为:[ ‘a‘,‘c‘, ‘b‘]