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递归实现快速排序
快速排序(QuickSort)是对冒泡排序的一种改进: 基本思想: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序 过程可以递归进行,以此达到整个数据变成有序序列. 一趟快速排序的算法是: 1)设置两个变量i.j,排序开始的时候:i=0,j=N-1: 2)以第一个数组元素作为关键数据,赋值给key,即key=A[0]: 3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key
-
关于python之字典的嵌套,递归调用方法
一 字典的嵌套 在机器学习实战决策树部分,生成决策树时用到了字典的嵌套. >>>s1={'no surface':{}} >>>s1['no surfacce'][0]='no' >>>s1 {'no surface':{0:'no'}} >>>s2={'flipper':{}} >>>s2['flipper'][0]='no' >>>s2['flipper'][1]='yes' >>&
-
Python理解递归的方法总结
递归 一个函数在执行过程中一次或多次调用其本身便是递归,就像是俄罗斯套娃一样,一个娃娃里包含另一个娃娃. 递归其实是程序设计语言学习过程中很快就会接触到的东西,但有关递归的理解可能还会有一些遗漏,下面对此方面进行更加深入的理解 递归的分类 这里根据递归调用的数量分为线性递归.二路递归与多重递归 线性递归 如果一个递归调用最多开始一个其他递归调用,我们称之为线性递归. 例如: def binary_search(data, target, low, high): """ 二分查
-
python 递归深度优先搜索与广度优先搜索算法模拟实现
一.递归原理小案例分析 (1)# 概述 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! (2)# 写递归的过程 1.写出临界条件 2.找出这一次和上一次关系 3.假设当前函数已经能用,调用自身计算上一次的结果,再求出本次的结果 (3)案例分析:求1+2+3+...+n的数和 # 概述 ''' 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! ''' # 写递归的过程 ''' 1.写出临界条件 2.找出这一次和上一次关系 3.假设
-
Python基于递归算法求最小公倍数和最大公约数示例
本文实例讲述了Python基于递归算法求最小公倍数和最大公约数.分享给大家供大家参考,具体如下: # 最小公倍数 def lcm(a, b, c=1): if a * c % b != 0: return lcm(a, b, c+1) else: return a*c test_cases = [(4, 8), (35, 42), (5, 7), (20, 10)] for case in test_cases: print('lcm of {} is {}'.format(*case, lcm
-
python 列表递归求和、计数、求最大元素的实例
利用python的递归来执行求和.计数.求最大元素的方法简直溜到爆,这里粘贴一下代码: 列表的递归求和: def sum(list): if list==[]: return 0 return list[0]+sum(list[1:]) 测试: print sum([3,4,2,3]) 列表的递归计数: def countElem(list): if list==[]: return 0 return 1+countElem(list[1:]) 测试: print countElem([3,4,
-
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} 则全排列就是
-
python非递归全排列实现方法
刚刚开始学习python,当前看到了函数这一节.结合数组操作,写了个非递归的全排列生成.原理是插入法,也就是在一个有n个元素的已有排列中,后加入的元素,依次在前,中,后的每一个位置插入,生成n+1个新的全排列.因为Python切割数组或者字符串,以及合并比较方便,所以,程序会节省很多代码. def getArrayInsertCharToStr(STR,CHAR): arr =[] s_len = len(STR) index =0 while index <= s_len: #分割字符串 ar
-
Python递归生成全排列序列实操
目录 前言 代码 测试结果 前言 在生成数据的过程中,我们有时候需要基于已有的数据生成排列组合的序列,对此,我们需要编写全排列算法生成序列,本文将分享本人编写的递归实现的全排列算法,支持对任意类型的数据进行生成全排列序列(不局限于数字) 全排列: 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列.当m=n时所有的排列情况叫全排列. 全排列数: f(n)=n!(定义0!=1)f(n)=n!(定义0!=1) 递归实现方法: 要求长度为n的序列
-
python通过yield实现数组全排列的方法
本文实例讲述了python通过yield实现数组全排列的方法.分享给大家供大家参考.具体分析如下: 从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] = a
-
Python递归遍历列表及输出的实现方法
本文实例讲述了Python递归遍历列表及输出的实现方法.分享给大家供大家参考.具体实现方法如下: def dp(s): if isinstance(s,(int,str)): print(s) else: for item in s: dp(item) l=['jack',('tom',23),'rose',(14,55,67)] dp(l) 运行结果如下: jack tom 23 rose 14 55 67 希望本文所述对大家的Python程序设计有所帮助.
-
python递归删除指定目录及其所有内容的方法
实例如下: #! /usr/bin/python # -*- coding: utf-8 -*- import os def del_dir_tree(path): ''' 递归删除目录及其子目录, 子文件''' if os.path.isfile(path): try: os.remove(path) except Exception, e: #pass print e elif os.path.isdir(path): for item in os.listdir(path): itempa
-
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[:] h
-
全排列算法的非递归实现与递归实现的方法(C++)
(一)非递归全排列算法基本思想是: 1.找到所有排列中最小的一个排列P. 2.找到刚刚好比P大比其它都小的排列Q, 3.循环执行第二步,直到找到一个最大的排列,算法结束.下面用数学的方法描述:给定已知序列 P = A1A2A3An ( Ai!=Aj , (1<=i<=n , 1<=j<=n, i != j ) )找到P的一个最小排列Pmin = P1P2P3Pn 有 Pi > P(i-1) (1 < i <= n)从Pmin开始,总是目
-
python 递归调用返回None的问题及解决方法
今天在做python获取邮件时需要递归调用解析函数才可以解析邮件内容,最后想要将解析出的内容返回时发现返回的是None 可以内容却可以打印出来,很费解.后来在网上找到了解决方案,才想明白 在这里记录下. 原文:https://www.jb51.net/article/182765.htm 原始测试代码如下: def print_info(msg, indent=0): if indent == 0: for header in ['From', 'To', 'Subject']: value =
-
python实现文法左递归的消除方法
前言 继词法分析后,又来到语法分析范畴.完成语法分析需要解决几个子问题,今天就完成文法左递归的消除. 没借鉴任何博客,完全自己造轮子. 开始之前 文法左递归消除程序的核心是对字符串的处理,输入的产生式作为字符串,对它的拆分.替换与合并操作贯穿始终,处理过程的逻辑和思路稍有错漏便会漏洞百出. 采用直接改写法,不理解左递归消除方法很难读懂代码. 要求 CFG文法判断 左递归的类型 消除直接左递归和间接左递归 界面 源码 import os import tkinter as tk import tk
随机推荐
- php的计数器程序
- 详解Java豆瓣电影爬虫——小爬虫成长记(附源码)
- spring batch 读取多个文件数据导入数据库示例
- Java利用HttpClient模拟POST表单操作应用及注意事项
- 利用Python实现简单的相似图片搜索的教程
- 一些javascript一些题目的解析
- Python中用于计算对数的log()方法
- C#操作Clipboard读取剪切板中数据实例详解
- Android时光轴实现淘宝物流信息浏览效果
- Python md5与sha1加密算法用法分析
- SQLServer中merge函数用法详解
- 基于Java中的数值和集合详解
- 分析Node.js connect ECONNREFUSED错误
- Java实现的简易记事本
- Android开发之OkHttpUtils的具体使用方法
- 简单易用的计数器(数据库)
- Android Studio 当build时候出错解决办法
- MySQL 8 新特性之Invisible Indexes
- Android仿QQ空间顶部条背景变化效果
- PHP面向对象程序设计之接口的继承定义与用法详解