难度:★★★☆☆
类型:数学
方法:回溯法
给定一个没有重复数字的序列,返回其所有可能的全排列。
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
全排列其实可以使用python内置的permutations函数,例如求['a', 'b', 'c']的全排列,可以使用:itertools.permutations(['a', 'b', 'c'],3)快速得到。这里参考了 大佬博客 。
我们举个例子,以字符串列表['a', 'b', 'c']为例,我们逐个位确定全排列的所有可能。回溯法的原理在于在前n-1位元素确定的情况下,求取n位以后的全排列。本例中,首先固定第0位,就是分别将第0位与它本身及后面各位元素交换,得到3种不同的可能,在固定这一位后,在考虑第1位的可能性,将第1位与它本身及其后元素交换,有两种可能性,当前两位元素确定后,最后一位只有一种可能性。因此一共有6种可能。
这里需要注意的是,每次交换元素并回溯寻找后,都要将元素交换回来,保持没有交换前的状态。
与回溯法类似,增加临时列表用来存储是否查看过变量。
如有疑问或建议,欢迎评论区留言~
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
示例 1:
输入:nums = [1,1,2]
输出:
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
源码:
运行结果:
以上四种情况均为最常见的排列组合,从有无顺序和是否重复两个维度进行思考,建议理解并背诵。
在使用python计算排列组合之前,需要计算阶乘,可以有两种方式,一是使用math库中的factorial函数,二是使用如下的递归函数。
按照排列的公式:
按照组合的公式:
3.1 生日问题
假设一个班级中共有n个人,一年有365天,其中每天作为生日的概率是相等的,那么其中至少有两个人的生日在同一天的概率是多少?
此题属于全排列问题,需要反向思考,写出公式之后直接输入到python中计算
3.2 大乐透问题
大乐透的玩法是这样的,从35个红球中选择5个,从12个红球中选择2个,如果全中,那就中一等奖。那么请问,中一等奖的概率是多少?
此题属于组合问题,中奖的可能性为一种,因此分子为1,分母为所有的组合情况。