如果第一次閱讀本系列文檔請先移步閱讀【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.

需得：由π變?yōu)棣玫姆D距離drev(π,γ)，以及由π變?yōu)棣玫姆D路徑的集合，如果有多條符合要求的路徑，給出一條即可。

?

測試數(shù)據(jù)

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距離的計算中，我們了解到：檢查不匹配的符號，就可以推斷出兩個基因串之間進化路徑上發(fā)生的一系列點突變。在42 翻轉距離與廣度優(yōu)先搜索中，我們知道基因組還可以通過倒位法發(fā)生進化。同理，列舉出翻轉過程，我們能推理出一個序列是怎樣通過倒位逐步變成另一個的，并可計算出反轉距離。

? ? ? ? 本問題就是要求我們除了算出翻轉距離，還要給出翻轉過程。翻轉可以由發(fā)生翻轉的兩個端點處的位置進行標記，例如，將（4,1,2,6,3,5）轉換為（4,1,3,6,2,5）的翻轉用[3,5]進行表示。

?

思路

? ? ? ?與42 翻轉距離與廣度優(yōu)先搜索相同，這道題的解答同樣復制于網(wǎng)絡（https://github.com/fernandoBRS/Rosalind-Problems/blob/master/sort.py），且復制于同一人，所以很多內容不再重復，閱讀本部分代碼前請務必回顧一下42 翻轉距離與廣度優(yōu)先搜索的內容。

? ? ? ?本題只在之前的基礎上增加了給出翻轉過程的要求，因此代碼也是在上次的基礎上添加了滿足這個需求的內容。簡單來說，這里用history變量在逐層深入的過程中把翻轉過程記錄了下來，具體不再贅述，詳見代碼及注釋。

??

代碼