递归实现Ann全排列的枚举(基于Python)

本文1118字;预计阅读8分钟;

在写一些概率统计题的模拟时,经常需要把A(n,n)、C(n,m)的排列组合全部列出来,这里记录一下A(n,n)全排列全部遍历的实现。根据概率论中的排列组合知识知道A(n,n)=n!=n*(n-1)…*1;最终结果的数量一共有n的阶乘,例如对于集合{1,2,3},有6种全排列。

要枚举出所有的排列结果,我们从n=1开始来看,集合{1}的全排列就是{1},n=2时,有 {1,2} 和 {2,1} ,可以看成是2和1交换位置,然后对{1}进行全排列;对{1,2,3},先2和1交换,得到{2}和{1,3},对{1,3}采用和n=2的情况相同的处理,所以是可以递归的,于是采用递归来写,递归终止条件可以用n=1,也可以在n=2的时候就交换然后返回,归纳一下是将每个元素放到余下n-1个元素组成的队列最前方,对剩余元素进行递归全排列。用Python翻译这一思路:

def perm(lst): #input:list, 一个字符串格式的元素列表
   n=len(lst)
   if n<=1:
       return lst
   elif n==2:
       return [lst[0]+lst[1],lst[1]+lst[0]] #终止条件
   kk=[]
   for i in range(n):
       nlst=lst[0:i]+lst[i+1:] #除lst[i]外的元素
       c=perm(nlst)
       ss=[lst[i]+j for j in c]
       kk.extend(ss) #注意是extend不是append
   return kk

上面perm函数被递归调用了。输出格式是一个一维的数组。测试:

s=perm(['1','2','3'])  #perm(list('123'))print(s)#['123', '132', '213', '231', '312', '321']

看一篇文章发现leetcode上正好有一个全排列的题:

Given a collection of distinct integers, return all possible permutations.

Example: Input: [1,2,3] Output:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

简单说就是给定一个没有重复数字的序列,返回其所有可能的全排列。不过其输入是一个整数数值列表,输出期望是二维数组。

简单改一下刚才写的代码:

class Solution(object):
    def permute(self, nums):
        """
        :type lst: List[int]
        :rtype: List[List[int]]
        """
        n=len(nums)
        if n<=1:
            return [nums]
        elif n==2:
            return [[nums[0],nums[1]],[nums[1],nums[0]]]
        kk=[]
        for i in range(n):
            nlst=nums[0:i]+nums[i+1:] 
            c=self.permute(nlst)
            ss=[]
            for j in c:
                w=[nums[i]]
                w.extend(j)
                ss.append(w)
            kk.extend(ss)
        return kk

通过了测试:

leetcode第46题提交结果

另外发现Python的库itertools有很好用的轮子:permutations和product,列出全排列很方便:

from itertools import permutations
print(list(permutations('1234')))

而且permutations支持两个参数,例如permutations('ABCD', 2)得到AB AC AD BA BC BD CA CB CD DA DB DC,就是从ABCD中任选两个排列,A(4,2)。官方文档给出了permutations(iterable[, r])实现的等价代码,是很好的参考资料。

具体关于permutations和product,可以看官方文档: itertools.permutations (https://docs.python.org/2/library/itertools.html#itertools.permutations)。

本文分享自微信公众号 - 蛰虫始航(lyns_sailing)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-12

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据实战演练

程序员如何保持竞争力

如果说哪个职业需要不断学习,那么程序员这个职业首屈一指。面对各式各样的技术栈,我们需要不断地进行学习来保持行业竞争力。

10620
来自专栏SuperFeng

一定要知道的Python内置数据结构

我喜欢 Python 的原因之一是因为它简单,短短几行代码就可以做很多事情。Python 内置了很强大的数据结构,我们可以直接用,不必像其他语言一样先构造数据结...

10730
来自专栏二狗的DBA之路

InnoDB全文索引基础

https://dev.mysql.com/doc/refman/5.6/en/fulltext-search.html

11030
来自专栏SuperFeng

我写了一个Python小项目

最近我写了一个 Python 练手小项目,它是一个 PC 桌面版的便签程序,很简陋。写这个小项目是为了熟悉一下用 Python 进行一个完整的项目开发,进一步熟...

17130
来自专栏铭毅天下

干货 | Elasticsearch7.X Scripting脚本使用详解

除了官方文档,其他能找到的介绍Elasticsearch脚本(Scripting)的资料少之又少。

37610
来自专栏python语言学习

django 路由系统

#注意事项 1 urlpatterns中的元素按照书写顺序从上往下逐一匹配正则表达式,一旦匹配成功则不再继续。 2 若要从URL中捕获一个值,只需要在它周围放置...

10730
来自专栏开源优测

为什么你学不会Appium

- 基于webdriver协议,看着眼熟不?没错就是和selenium webdriver同源的机制

10430
来自专栏前端桃园

非常全面的前端协作规范(长文建议先收藏)

原文链接:https://juejin.im/post/5d3a7134f265da1b5d57f1ed

17220
来自专栏二狗的DBA之路

replication-manager 编译

replication-manager 和 orchestrator  这2款软件是以后的趋势

10740
来自专栏PowerBI战友联盟

PowerBI 发布2019年路线图

PowerBI 的发展规划一直令人关注,今日,微软官方发布了PowerBI 2019年的路线图。本文挑选其中几个重点分享,详细信息请参考官方文档: 【Power...

14020

扫码关注云+社区

领取腾讯云代金券

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