如果第一次閱讀本系列文檔請(qǐng)先移步閱讀【ROSALIND】【練Python，學(xué)生信】00 寫(xiě)在前面 ?謝謝配合~

題目：

重建進(jìn)化歷程（Reconstructing Evolutionary Histories）

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

所給：一對(duì)排列π和γ，長(zhǎng)度都為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(zhuǎn)距離drev(π,γ)，以及由π變?yōu)棣玫姆D(zhuǎn)路徑的集合，如果有多條符合要求的路徑，給出一條即可。

?

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

1 2 3 4 5 6 7 8 9 10

1 8 9 3 2 7 6 5 4 10

測(cè)試輸出

2

4 9

2 5

?

生物學(xué)背景

? ? ? ? 在06 DNA序列Hamming距離的計(jì)算中，我們了解到：檢查不匹配的符號(hào)，就可以推斷出兩個(gè)基因串之間進(jìn)化路徑上發(fā)生的一系列點(diǎn)突變。在42 翻轉(zhuǎn)距離與廣度優(yōu)先搜索中，我們知道基因組還可以通過(guò)倒位法發(fā)生進(jìn)化。同理，列舉出翻轉(zhuǎn)過(guò)程，我們能推理出一個(gè)序列是怎樣通過(guò)倒位逐步變成另一個(gè)的，并可計(jì)算出反轉(zhuǎn)距離。

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

?

思路

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

? ? ? ?本題只在之前的基礎(chǔ)上增加了給出翻轉(zhuǎn)過(guò)程的要求，因此代碼也是在上次的基礎(chǔ)上添加了滿(mǎn)足這個(gè)需求的內(nèi)容。簡(jiǎn)單來(lái)說(shuō)，這里用history變量在逐層深入的過(guò)程中把翻轉(zhuǎn)過(guò)程記錄了下來(lái)，具體不再贅述，詳見(jiàn)代碼及注釋。

??

代碼