珲春市建设局网站,深圳网站制作服务公,动画设计专业学什么,做网站公司赚不赚钱目录
一.引言
二.排列 A-Permute
◆ 定义
◆ 计算
◆ 性质
◆ 实现
三.组合 C-Combine
◆ 定义
◆ 计算
◆ 性质
◆ 实现
四.经典算法题目
1.全排列 [无重复]
2.全排列 [有重复]
3.组合 [可重复]
4.子集 [无重复]
5.子集 [有重复]
五.总结 一.引言
关于排列…
目录
一.引言
二.排列 A-Permute
◆ 定义
◆ 计算
◆ 性质
◆ 实现
三.组合 C-Combine
◆ 定义
◆ 计算
◆ 性质
◆ 实现
四.经典算法题目
1.全排列 [无重复]
2.全排列 [有重复]
3.组合 [可重复]
4.子集 [无重复]
5.子集 [有重复]
五.总结 一.引言
关于排列前面已经介绍了一部分算法例如求数组的全排列求子集等等我们可以使用回朔的方法进行计算今天主要讲下数学上排列与组合的计算方式因为有一些题目可以巧妙地使用排列组合快速得到结果下面整理下定义与 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 个数字即 5x4x3ok 搞定了!
Tips:
如果从实际含义理解的话这是个无放回的问题6 个里面选 2 个第一次我们选一个人出来有 6 种可能由于不能重复所以现在还剩 5 个人我们再从 5 个人里面随便抓一个出来就凑齐 2 个人了所以是 6 x 5。 ◆ 性质 ◆ 实现
def factorial(num):计算阶乘result 1for i in range(1, num 1):result * ireturn resultdef 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 1for i in range(n):re * mm - 1return 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! ◆ 性质
若 ab n 则存在以下关系这个可以逆向思维理解一下这里就不多解释了: 根据公式也可以推导出特殊情况: ◆ 实现
def factorial(num):计算阶乘result 1for i in range(1, num 1):result * ireturn resultdef 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 1re 1for i in range(n):re * mm - 1return 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:continuerepeat.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:continuerepeat.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, n1) 的结果我们可以执行合并操作。 换递归的实现操作下:
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 组合12 和后面的 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:continueuset.add(nums[i])dfs(i 1, cur [nums[i]])dfs(0, [])return res 在前面求子集的基础上增加了 repeat 判重。 五.总结
上面整理了排列组合的相关定义与公式并在下面实现了几种常见的排列组合算法这几个算法大家可以熟练掌握应为很多问题的解决都可以使用这些方法直接简化我们的流程同时一些路径的问题使用排列组合公式可以直接出答案非常的方便。
Tips:
上面的代码解析在 分治与回溯 的章节里有详细的注释和分析过程。
