【Rosalind】Enumerating Gene Orders – 寻找全排列：dfs深度优先搜索算法

Rosalind习题：Enumerating Gene Orders （题目ID：PERM）

这道习题以基因组重排研究（Genome Rearrangement）为背景提出了一个有关于全排列的问题。

Problem

A permutation of length n is an ordering of the positive integers {1,2,…,n}. For example, π=(5,3,2,1,4) is a permutation of length 5.

Given: A positive integer n≤7.
Return: The total number of permutations of length n, followed by a list of all such permutations (in any order).

Sample Dataset

3

Sample Output

思路

这道题的意思非常简单，就是给出一个正整数n，首先返回元素数为n的不含相同元素的列表的全排列的数目，然后再分别按格式返回这些全排列。 我们应该知道n个不同元素的全排列数目应该是n!，也就是n的阶乘，那么这个数字是怎么来的？ 按照n=3的情况来说，就是任何排列会有3个位置，首先挑选一个元素放在第一个位置，有3种选法，然后再在剩下两个元素中挑选一个放在第二个位置，有2种选法，最后一个位置就放剩下那个，只有1种选法，所以根据乘法法则，应该就有321也就是3的阶乘——6种选法。 如果想下排列的格式，以n=4为例，我们先选1放在第一个位置，剩下的2,3,4的全排列就有6种，放在1的后面。类似地，选2放在第一个位置，剩下的1,3,4的6种全排列就放在2的后面。如此把4个数字放在第一位，分别都有6个排列，这样就是4*3!也就是4!=24种排列方法。 所以这里，我们实际上就用了递归的思想，刚学编程时学过的编写计算阶乘的函数实际上就是用到了这个思想，用数学语言来说可能就是f(n-1)吧！我的理解就是在函数内部调用函数本身。

递归完成阶乘的运算：

我的代码

另一种方法：深度优先算法

在博文https://blog.csdn.net/qq_31601743/article/details/82053201 还找到了另一种实现全排列的方法：

我自己理解了一下这段代码： 待排列的列表中有多少元素，就在visit列表里放入多少个开关（TrueorFalse）来控制每一个元素的使用（也是一种初始化）。然后提前创建放置了空元素的列表temp用来存放结果。 在像普通方法遍历时，每将arr中元素的一个数放进temp时，就把该元素的开关关掉（visit[index] = False），这一步在深度优先算法中被称为试探，然后在递归过程（dfs(position + 1)）结束后，一定要将该开关调回去，也就是visit[index] = True这一步，这一步在这个算法里称为回溯，如果不进行这一步，相当于这个数字在之后所有的排列中持续被占用了。 满足position == len(arr)时循环就结束了，这个时候temp被填满了，应该把当前一次的排列输出出来。

感想

这次在这个题目中学习到了这样的一种dfs算法，然后我在理解的过程中，观看了这个视频，分享给大家： dfs深度优先算法实现全排列讲解

这个视频不是讲Python的，不过大家可以听一下这个算法的讲解，还是很清楚的！

参考

1. https://blog.csdn.net/qq_31601743/article/details/82053201
2. https://blog.csdn.net/weixin_39910711/article/details/100692318
3. https://www.bilibili.com/video/av88267937