行业知识
【算法】——全排列算法讲解
2026-11-19 16:33:43
来源:互联网转载
前言:
今天,���给大家讲解的是关于全排列算。我会从三个方面去进行展开:
- 首先,我会给大家分析关于全排列算法的思想和定义;
- 紧接着通过手动实现出一个全排列代码来带大家见见是怎么实现的;
- 最后我会给出两道题帮助大家去进行理解记忆。
目录
前情摘要
(一)定义和公式讲解
1、定义
2、公式
(二)全排列的初始思想
(三)代码实现
1、递归不去重
2、递归去重
3、非递归实现
(四)题目讲解
1、字符串的排列
(五)总结
前情摘要
- 在今后的找工作中,全排列相对来说还是一个比较常见问题。不管是不是做算法岗的,在许多的大公司面试中都会考察应聘者有关全排列的问题(就算不让你编写完整代码,也会让你描述大致的思路)。接下来,我就带领大家去学习有关全排列的相关知识。
(一)定义和公式讲解
1、定义
- 全排列就是从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。
- 当m=n时所有的排列情况叫全排列。
- 简单点来说就是:全排列的含义就是一个序列所有的排序可能性
我们通过简单的举例带大家直观的认识一下:
假设现在数组中有【1 2 3】这样的三个元素,那么对其进行排列之后结果是什么呢?
我相信聪明的小伙伴们已经知道答案了,具体的如下:
- 123
- 132
- 213
- 231
- 321
- 312
假设现在数组中有【1 2 3 4】这样的四个元素,那么对其进行排列之后结果是什么呢?
具体的如下:
- 1234
- 1243
- 1324
- 1342
- 1432
- 1423
- 2134
- 2143
- 2314
- 2341
- 2431
- 2413
- 3214
- 3241
- 3124
- 3142
- 3412
- 3421
- 4231
- 4213
- 4321
- 4312
- 4132
- 4123
2、公式
因此,综上所述,我们可以发现全排列得到的结果的数量跟数学中的全排列问题是一样的
- 对于给定的序列,假设序列中 N个元素,对其进行全排列之后我们可以得到的排序数量为 N!
(二)全排列的初始思想
1、上述我给出了一个序列的全排列的结果以及全排列得到的最终的结果数量。
2、接下来,我简单的讲述一下上述全排列是如何得到的,对其具体的实现过程进行描述。
具体过程如下:
- 1、我们以上述数组中的【1 2 3 4】,这里是排序好的,为了更好的说明,我们以【2 1 3 4】为例;
- 2、首先,我们先保持第一个元素不变,即【2】不变,对数组中剩余的元素【1 3 4】进行排序;
- 3、同上,继续上述过程。此时我们保持剩余数组中的【1】不变,对【3 4】进行排序;
- 4、在往下遍历。保持【3】不变,对【4】对进行全排列,由于【4】只有一个,它的排列只有一种:4。因此上述完成之后我们可以得到一种排序结果,即【2 1 3 4】;
- 5、接下来因为【4】已经遍历过,所以不能在以【4】打头了。此时需要交换【3 4】这两个元素的位置,得到新的一种排序,即【2 1 4 3】 ;
- 6、完成上述的操作之后,此时【3 4】的情况都写完了,现在进行回溯,则不能以【1】打头了;
- 7、所以现在我们需要交换的对象就是【1 3】,依次类推,最终我们可以得到以【2】开头的排列有以下几种:
213421432314234124312413
- 8、在接下来就是改变第一个位置的元素,即通过剩余的【 1 3 4 】作为头元素,在重复上述过程即可得到最终的全排列结果。
(三)代码实现
通过上述的分析,我们不难发现一个问题那就是:
- 对于给定的序列,刚开始时我们知道序列的第一个元素,剩余的序列元素此时又可以看成是一个全排列的例子;
- 我们可以对剩余的序列进行与开始相同的操作,直到中只一个元素为止。这样我们就获得了所有的可能性。因此不难看出这是一个递归的过程。
接下来,我们简单的实现一下这样的代码:
1、递归不去重
- 思路如下:
- 求n位的字符串的全排列,先确定第0位,然后对后面n-1位进行全排列,在对n-1为进行全排列时,先确定第1位,然后对后面的n-2位进行全排列,...由此得到递归函数和递归的结束条件;
- 因此解决n-1位元素的全排列就能解决n位元素的全排列了。
- 代码如下:
//生成向量的所有排列void permute(string str, int left, int right){ //如果遍历到 left == right ,说明全排列已经做完了只需输出即可 if (left == right) cout
- 8、在接下来就是改变第一个位置的元素,即通过剩余的【 1 3 4 】作为头元素,在重复上述过程即可得到最终的全排列结果。