【ROSALIND】【练Python，学生信】51 用翻转过程重建进化历程

如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面  谢谢配合~

题目：

重建进化历程（Reconstructing Evolutionary Histories）

Given: Two permutations π and γ, each of length 10.

所给：一对排列π和γ，长度都为10。

Return: The reversal distance drev(π,γ), followed by a collection of reversals sorting π into γ. If multiple collections of such reversals exist, you may return any one.

需得：由π变为γ的翻转距离drev(π,γ)，以及由π变为γ的翻转路径的集合，如果有多条符合要求的路径，给出一条即可。

测试数据

1 2 3 4 5 6 7 8 9 10

1 8 9 3 2 7 6 5 4 10

测试输出

2

4 9

2 5

生物学背景

        在06 DNA序列Hamming距离的计算中，我们了解到：检查不匹配的符号，就可以推断出两个基因串之间进化路径上发生的一系列点突变。在42 翻转距离与广度优先搜索中，我们知道基因组还可以通过倒位法发生进化。同理，列举出翻转过程，我们能推理出一个序列是怎样通过倒位逐步变成另一个的，并可计算出反转距离。

        本问题就是要求我们除了算出翻转距离，还要给出翻转过程。翻转可以由发生翻转的两个端点处的位置进行标记，例如，将（4,1,2,6,3,5）转换为（4,1,3,6,2,5）的翻转用[3,5]进行表示。

思路

       与42 翻转距离与广度优先搜索相同，这道题的解答同样复制于网络（https://github.com/fernandoBRS/Rosalind-Problems/blob/master/sort.py），且复制于同一人，所以很多内容不再重复，阅读本部分代码前请务必回顾一下42 翻转距离与广度优先搜索的内容。

       本题只在之前的基础上增加了给出翻转过程的要求，因此代码也是在上次的基础上添加了满足这个需求的内容。简单来说，这里用history变量在逐层深入的过程中把翻转过程记录了下来，具体不再赘述，详见代码及注释。

代码