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

題目：

翻轉(zhuǎn)距離（Reversal Distance）

Given: A collection of at most 5 pairs of permutations, all of which have length 10.

所給：不超過5對(duì)長(zhǎng)度為10的排列。

Return: The reversal distance between each permutation pair.

需得：每隊(duì)排列之間的翻轉(zhuǎn)距離。

?

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

1 2 3 4 5 6 7 8 9 10

3 1 5 2 7 4 9 6 10 8

?

3 10 8 2 5 4 7 1 6 9

5 2 3 1 7 4 10 8 6 9

?

8 6 7 9 4 1 3 10 2 5

8 2 7 6 9 1 5 3 10 4

?

3 9 10 4 1 8 6 7 5 2

2 9 8 5 1 7 3 4 6 10

?

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

測(cè)試輸出

9 4 5 7 0

?

生物學(xué)背景

????????倒位指染色體發(fā)生斷裂后，某一區(qū)段顛倒180°后重新連接。這是一種很常見的染色體結(jié)構(gòu)變異。一個(gè)基因組變成另一個(gè)基因組所需的最小次數(shù)稱為翻轉(zhuǎn)距離（Reversal Distance），可以用于遺傳學(xué)研究。

?

Python背景? ?

????????這道題對(duì)于我來說難度實(shí)在太太太太大了，我在與它死磕了幾天、心態(tài)崩潰了好幾次之后終于放棄了。本題代碼復(fù)制自（https://github.com/fernandoBRS/Rosalind-Problems/blob/master/rear.py）。所以這次讓我們一起圍觀真正的大神的代碼。當(dāng)然在開始之前需要了解一些相關(guān)知識(shí)。

????????第一個(gè)知識(shí)點(diǎn)是 __name__ == "__main__" 的含義，詳情可看這個(gè)鏈接（https://blog.csdn.net/anshuai_aw1/article/details/82344884）。簡(jiǎn)單來說，這個(gè)語句以下的代碼僅在該P(yáng)ython文件被直接運(yùn)行時(shí)起作用，如果該文件作為一個(gè)模塊被其他文件調(diào)用，則之下的代碼被忽視。

????????第二個(gè)知識(shí)點(diǎn)是Python中的collection模塊，詳情可看這個(gè)鏈接（https://www.jianshu.com/p/8d635f881a63）。這個(gè)模塊中有很多維護(hù)字典的方法，在本代碼中大量使用。

????????第三需要了解元組（tuple）。這是Python中的一種重要數(shù)據(jù)結(jié)構(gòu)，結(jié)構(gòu)和使用與列表相似，差別在于其中元素不能修改，且形式是用小括號(hào)括起來。

????????第四，yield關(guān)鍵字。解釋可參考鏈接（https://blog.csdn.net/mieleizhi0522/article/details/82142856/）。包含這個(gè)關(guān)鍵字的函數(shù)起生成器作用。

?

思路

????????由于本題代碼復(fù)制于網(wǎng)絡(luò)，我只根據(jù)自己的理解猜測(cè)作者的思路，歡迎糾錯(cuò)！

????????本題含義是一個(gè)序列內(nèi)部發(fā)生幾次翻轉(zhuǎn)可以變成另一個(gè)序列，本質(zhì)上是一個(gè)廣度優(yōu)先搜索問題，具體算法內(nèi)容可參考這篇文章（https://blog.csdn.net/moonlightpeng/article/details/89636650）。

????????我認(rèn)為作者在這里的基本思路是固定一個(gè)排列不變，枚舉另一個(gè)排列所能形成的所有排列，然后是新形成的排列的所有排列，以此類推。同時(shí)優(yōu)先檢查翻轉(zhuǎn)次數(shù)最少的排列，如果找到了和目標(biāo)排列相同的排列，其翻轉(zhuǎn)次數(shù)即為做少的翻轉(zhuǎn)次數(shù)。不過作者在此基礎(chǔ)上做了些改進(jìn)，采用了一種“兩頭堵”的策略，因?yàn)檫@種樹形結(jié)構(gòu)深度越深，形成的分叉會(huì)急劇增加。作者人為將深度控制在了五層，如果到達(dá)這個(gè)深度依然沒找到目標(biāo)排列，就從另一頭開始找，直至在中間碰面，把兩次的翻轉(zhuǎn)數(shù)相加就是最終結(jié)果。（至于為什么是5次、4次，我想是因?yàn)閷?duì)于一個(gè)長(zhǎng)度為10的序列，翻轉(zhuǎn)9次就可以得到任一排列。）

????????我不知道自己理解的是否準(zhǔn)確，也不知道是否把這個(gè)問題講明白了。歡迎讀到這里的小伙伴參與交流討論！

?

代碼

import collections

def get_all_permutations(s): # 起生成器作用的函數(shù)，作用是依次生成排列
??? for i in range(len(s)):
??????? for j in range(i + 2, len(s) + 1):
??????????? yield s[:i] + s[i:j][::-1] + s[j:]


def get_reversal_distance(p1, p2): # 計(jì)算翻轉(zhuǎn)距離的函數(shù)
??? if p1 == p2: # 如果兩個(gè)排列相等，可以直接返回翻轉(zhuǎn)距離為0
??????? return 0

??? target = tuple(p2) # 排列p2作為翻轉(zhuǎn)的目標(biāo)排列
??? fromfirst = {tuple(p1): 0} # 創(chuàng)建字典，key為排列，value為初始排列翻轉(zhuǎn)幾次能得到該排列，先把p1放進(jìn)去
??? q = collections.deque((p1,)) # deque是一種數(shù)據(jù)對(duì)象，類似列表，但插入和刪除的效率更高。創(chuàng)建這么一個(gè)對(duì)象q，? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #并把p1放進(jìn)去。不難發(fā)現(xiàn)，q中數(shù)據(jù)是按翻轉(zhuǎn)次數(shù)排列的。

??? while len(q): # 如果q中還有排列，就繼續(xù)循環(huán)
?? ?????s = q.popleft() # 把q中第一個(gè)排列移除，放到s中
??????? c = fromfirst[s] # 從字典中查出來該排列對(duì)應(yīng)的翻轉(zhuǎn)次數(shù)

??????? for j in get_all_permutations(s): # j接受生成器產(chǎn)生的排列
??????????? if j == target: # 如果新產(chǎn)生的排列和目標(biāo)排列相同，意味著最小翻轉(zhuǎn)次數(shù)找到了，就可以把次數(shù)直接返回輸出了
??????????????? return c + 1

??????????? if not j in fromfirst: # 如果排列還不在字典里，把它添加進(jìn)去
??????????????? fromfirst[j] = c + 1

??????????????? if c != 4: # 如果翻轉(zhuǎn)已經(jīng)超過5次了，就先停止，不再記錄次數(shù)更多的排列
??????????????????? q.append(j)

??? # 如果之前的5次翻轉(zhuǎn)都沒翻轉(zhuǎn)出目標(biāo)排列，就從另一頭開始
??? fromsecond = {tuple(p2): 0} # 創(chuàng)建新的字典，key為排列，value為初始排列翻轉(zhuǎn)幾次能得到該排列，把p2放進(jìn)去
??? target = tuple(p1) # 這次以排列p1作為翻轉(zhuǎn)的目標(biāo)排列
??? q = collections.deque((p2,)) # 把p2排列放進(jìn)q
??? answer = 100000

??? while len(q): # 和上個(gè)翻轉(zhuǎn)循環(huán)過程含義相同，這次翻轉(zhuǎn)不超過4次
??????? s = q.popleft()
??????? c = fromsecond[s]

??????? if c == 4:
???????? ???break

??????? for j in get_all_permutations(s):
??????????? if j == target:# 如果新產(chǎn)生的排列和目標(biāo)排列相同，意味著最小翻轉(zhuǎn)次數(shù)找到了，就可以把次數(shù)直接返回輸出了
??????????????? return c + 1

??????????? if not j in fromsecond:
??????????????? fromsecond[j] = c + 1

??????????????? if c != 3:
??????????????????? q.append(j)

??????????? if j in fromfirst: # p2經(jīng)過翻轉(zhuǎn)和第一次翻轉(zhuǎn)循環(huán)產(chǎn)生的某個(gè)排列相同
??????????????? answer = min(answer, fromfirst[j] + fromsecond[j]) # 把兩次翻轉(zhuǎn)的次數(shù)相加即為最終結(jié)果
??? return answer


if __name__ == "__main__": # 決定以下代碼是否需要運(yùn)行
??? distances = []

??? with open('rosalind_rear.txt') as s:
??????? dataset = list(map(str.strip, s.readlines())) # 用map函數(shù)讀入題目

??? for i in range(0, len(dataset), 3): # 整理輸入數(shù)據(jù)
??????? s = tuple(map(int, dataset[i].split()))
??????? t = tuple(map(int, dataset[i + 1].split()))

??????? distances.append(get_reversal_distance(t, s))

??? print(' '.join(map(str, distances))) # 結(jié)果輸出