python递归全排列实现方法

yipeiwu_com5年前Python基础

本文实例为大家分享了python递归全排列的实现方法,供大家参考,具体内容如下

排列:从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如下:

COUNT=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

最后输出的结果如下:

======================== RESTART: D:/Python27/perm.py ========================
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 3, 2]
[1, 4, 2, 3]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 3, 1]
[2, 4, 1, 3]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 2, 3, 1]
[4, 2, 1, 3]
[4, 3, 2, 1]
[4, 3, 1, 2]
[4, 1, 3, 2]
[4, 1, 2, 3]
24
>>> 

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

python滑块验证码的破解实现

python滑块验证码的破解实现

破解滑块验证码的思路主要有2种: 获得一张完整的背景图和一张有缺口的图片,两张图片进行像素上的一一对比,找出不一样的坐标。 获得一张有缺口的图片和需要验证的小图,两张图片进行二...

Python将list中的string批量转化成int/float的方法

最近在处理词向量这块,因为平时习惯把处理的词向量保存成文件,但是txt文件读取出来的都是string格式的数字,有必要转成float型 上网查了一下教程,在这记录一下: data =...

关于pytorch处理类别不平衡的问题

当训练样本不均匀时,我们可以采用过采样、欠采样、数据增强等手段来避免过拟合。今天遇到一个3d点云数据集合,样本分布极不均匀,正例与负例相差4-5个数量级。数据增强效果就不会太好了,另外过...

Python实现公历(阳历)转农历(阴历)的方法示例

Python实现公历(阳历)转农历(阴历)的方法示例

本文实例讲述了Python实现公历(阳历)转农历(阴历)的方法。分享给大家供大家参考,具体如下: 两个要点: 1、公历转农历用了查表法(第126行) 2、节气用了天文法?(第176行)...

python常见排序算法基础教程

python常见排序算法基础教程

前言:前两天腾讯笔试受到1万点暴击,感觉浪费我两天时间去牛客网做题……这篇博客介绍几种简单/常见的排序算法,算是整理下。 时间复杂度 (1)时间频度一个算法执行所耗费的时间,从理论上是不...