目录
一.引言
关于排列前面已经介绍了一部分算法，例如求数组的全排列，求子集等等，我们可以使用回朔的方法进行计算，今天主要讲下数学上排列与组合的计算方式，因为有一些题目可以巧妙地使用排列组合快速得到结果，下面整理下定义与 Python 实现方式。
二.排列 A-Permute
◆ 定义
排列公式采用如下形式:
其中 6、2 代表从 6 个元素里面选 2 个排列起来，注意这一要求有顺序 !
丽茹从 1-6 中选 2 个数字组成两位数，这个结果就是 A(6, 2)
又丽茹从 1-6 编号的同学中，一个当数学课代表，一个当语文课代表，那结果也是 A(6, 2)
◆ 计算
这是百度百科关于排列的定义和计算公式，下面我们简化下流程方便记忆:
有一个好记的方法，只要 A(m, n) 出来，我们就从 m! 开始往后写，写到第 n 个数字停止即可。例如 A(5, 3) 我们从 5 开始往后写 3 个数字即 5x4x3，ok 搞定了!
Tips:
如果从实际含义理解的话这是个无放回的问题，6 个里面选 2 个，第一次我们选一个人出来有 6 种可能，由于不能重复，所以现在还剩 5 个人，我们再从 5 个人里面随便抓一个出来就凑齐 2 个人了，所以是 6 x 5。
◆ 性质
◆ 实现
def factorial(num):
"""计算阶乘"""
result = 1
for i in range(1, num + 1):
result *= i
return result
def permutation(m, n):
"""计算排列 A(m, n)"""
return factorial(m) // factorial(m-n)计算两个阶乘相除即可，当然按照我们红色字体部分，我们可以快速计算，避免 (m-n)！的重复计算。
def fast_permutation(m, n):
if m == 1:
return 1
# 从 m 开始往后乘 n 次完活
re = 1
for i in range(n):
re *= m
m -= 1
return re三.组合 C-Combine
◆ 定义
组合公式采用如下形式:
其中 6、2 代表从 6 个元素里面选 2 个组合起来，注意这里 无顺序 !
丽茹从 1-6 中选 2 个数字，这个结果就是 C(6, 2)
又丽茹从 1-6 编号的同学中选两个打扫卫生，那结果也是 C(6, 2)
◆ 计算
还是先把长长的公式掏出来，下面我们简化下流程方便记忆:
有一个好记的方法，对于给定的 m、n，分母 m 从大往小写 n 个，分子从 1 到 n 写下来 。例如 C(6, 2) 直接 6 从大到小写 2 个即 6x5，再从 1写到 n，即 1x2，除去吧，一除一个不知道。
Tips:
继续从实际情况下理解一下，首先这里还是无放回的问题，我们第一次能够取 m 个，下一次能取 m-1 个，依次类推。以 (3, 2) 为例，我们可以取 (1, 2) (1, 3)、(2,1) (2,3)、(3,1),(3,2)，2个数字的组合 (1,2)、(2,1) 是一样的，所以我们重复了，重复了多少次就和 n 有关系了，n 能够排列 n! 种组合，所以就是 3 * (3-1) 直到 n 也就是 3 * 2，重复的话是 2! = 2 * 1，所以一共就 3 种组合 (1, 2)、(1、3)、(2, 3)。即 A(m, n) / n!
◆ 性质
若 a+b = n 则存在以下关系，这个可以逆向思维理解一下，这里就不多解释了:
根据公式也可以推导出特殊情况:
◆ 实现
def factorial(num):
"""计算阶乘"""
result = 1
for i in range(1, num + 1):
result *= i
return result
def combination(m, n):
"""计算排列 A(m, n)"""
return factorial(m) // factorial(m-n) // factorial(n)套公式的话按上面的方法写，也可以用我们红字的快速计算方法，避免重复计算。按照这个公式直接套用即可 C(m, n) = A(m, n) / n!
def fast_combination(m, n):
if m == 1:
return 1
re = 1
for i in range(n):
re *= m
m -= 1
return re // factorial(n)四.经典算法题目
下面四个题目来自: Python - Divide Conquer 分治 & Backtrack 回朔
1.全排列 [无重复]
全排列[无重复]: https://leetcode-cn.com/problems/permutations/
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
re = []
def dfs(position):
if position == len(nums) - 1:
re.append(nums[:])
# 固定第一个位置，再寻找下一个位置，循环
for i in range(position, len(nums)):
nums[position], nums[i] = nums[i], nums[position]
dfs(position + 1)
nums[position], nums[i] = nums[i], nums[position]
dfs(0)
return re这里 for i in range(position, len(nums)) 就是一个不断逼近的过程，就像 A(m,m) 一样，第一次有 m 个选择，下一次有 m-1 个选择，一直循环到最后一个数字。
上面这版交换索引不好理解的话，就用我们全排列的思想，固定第一个无放回，从剩下的找，这里无放回的操作我们使用 set，用过的就放到 set 不能用了：
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
re = []
def dfs(cur, used):
if len(cur) == len(nums):
re.append(cur[:])
for i in range(0, len(nums)):
if nums[i] in used:
continue
# 下一层进发
cur.append(nums[i])
used.add(nums[i])
dfs(cur, used)
# 恢复状态
cur.pop()
used.remove(nums[i])
used = set()
dfs([], used)
return re
2.全排列 [有重复]
全排列[有重复]: https://leetcode.cn/problems/permutations-ii/
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
re = []
def dfs(position):
if position == len(nums) - 1:
re.append(nums[:])
repeat = set()
for i in range(position, len(nums)):
if nums[i] in repeat:
continue
repeat.add(nums[i])
nums[position], nums[i] = nums[i], nums[position]
dfs(position + 1)
nums[position], nums[i] = nums[i], nums[position]
dfs(0)
return re固定第一个位置，固定第二个位置依次类推，这里变换位置时，如果有重复就不再变换了，排除这次的结果。
同理，我们可以使用人脑思维，即固定一个，再找剩下的不过同理需要进行去重操作:
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
re = []
def dfs(cur, used):
if len(cur) == len(nums):
re.append(cur[:])
repeat = set()
for i in range(0, len(nums)):
# 当前索引用过了 或者 当前元素重复了
if i in used or nums[i] in repeat:
continue
repeat.add(nums[i])
# 下一层进发
cur.append(nums[i])
used.add(i)
dfs(cur, used)
# 恢复状态
cur.pop()
used.remove(i)
used = set()
dfs([], used)
return re加了两个 set 没想到效率就是不一样。
3.组合 [可重复]
组合: https://leetcode.cn/problems/combinations/description/
class Solution(object):
def combine(self, n, k):
res = []
def dfs(cur, position):
if len(cur) == k:
res.append(cur[:])
return
for i in range(position, n):
cur.append(i + 1)
dfs(cur, i + 1)
cur.pop()
dfs([], 0)
return res[0, 1, 2, 3] 固定 0，再去找 123 组合、再固定 1 去找 23 组合，直到最后结束。
4.子集 [无重复]
子集: https://leetcode.cn/problems/subsets/description/
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = [[]]
# 遍历每个数字
for i in nums:
res = res + [[i] + re for re in res]
return res
不断累加 res 的值，最终得到全部的子集结果。当然这个题其实可以用组合来配合，因为全部的子集就是 C(n,i) for i in range(0, n+1) 的结果，我们可以执行合并操作。
换递归的实现操作下:
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
n = len(nums)
def dfs(position, cur):
res.append(cur)
for i in range(position, n):
dfs(i + 1, cur + [nums[i]])
dfs(0, [])
return res
上图可以方便大家理解本题，相当于 1 和后面的 2、3 组合，1，2 和后面的 3 组合，1 和 3 组合以此类推。
5.子集 [有重复]
子集: https://leetcode.cn/problems/subsets-ii/
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
n = len(nums)
nums.sort()
def dfs(position, cur):
res.append(cur)
uset = set()
for i in range(position, n):
if nums[i] in uset:
continue
uset.add(nums[i])
dfs(i + 1, cur + [nums[i]])
dfs(0, [])
return res在前面求子集的基础上增加了 repeat 判重。
五.总结
上面整理了排列组合的相关定义与公式，并在下面实现了几种常见的排列组合算法，这几个算法大家可以熟练掌握，应为很多问题的解决都可以使用这些方法直接简化我们的流程，同时一些路径的问题使用排列组合公式可以直接出答案，非常的方便。
Tips:
上面的代码解析在 分治与回溯 的章节里有详细的注释和分析过程。
