【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
Share this page if you like this post:)