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

題目：

枚舉有方向的基因序列（Enumerating Oriented Gene Orderings）

Given: A positive integer n≤6.

所給：一個不大于6的正整數(shù)n。

Return: The total number of signed permutations of length n, followed by a list of all such permutations (you may list the signed permutations in any order).

需得：由長度為n的數(shù)字組成的全排列（有正負符號）的數(shù)量，以及所有的排列方式（由任意順序給出）。

?

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

2

測試輸出

8

-1 -2

-1 2

1 -2

1 2

-2 -1

-2 1

2 -1

2 1

?

生物學背景

????????在之前的問題中，我們已經(jīng)知道親緣關系相近的物種往往也有相似的基因組，染色體通過其上基因的重排發(fā)生改變。我們也用排列的方式模擬了這種改變。然而在實際中，基因組是有方向的，很多時候轉錄只能沿一個方向進行。這樣我們就需要在原先的排列模型中引入正負符號，從而代表基因的方向。

?

數(shù)學背景

????????有符號的排列是在排列的基礎上給每個元素加上正負號。

?

思路

????????我把這道題看成兩個部分：1）n個數(shù)字看成n個組，每組2個元素，分別為n和-n，每組抽取一個組合起來，這樣我們就得到了2^n個組合。2）對每個組合再進行全排列，每個組合有n!個排列方式。這樣就可以得到所有的有符號排列情況。分別為這兩部分編寫代碼即可，代碼較為混亂繁復，僅供參考。

?

代碼

def perm(seq, begin, end):
??? """進行全排列的函數(shù)"""
??? global num
??? if begin == end:
??????? print(" ".join(seq))
??????? num += 1
??? else:
??????? for index in range(begin, end):
??????????? seq[index], seq[begin] = seq[begin], seq[index]
??????????? perm(seq, begin + 1, end)
??????????? seq[index], seq[begin] = seq[begin], seq[index]

def comb(s, k):
??? """輔助進行元素抽取的函數(shù)"""
??? if k == 0:
??????? return ['']
??? subseq = []
??? for i in range(len(s)):
??????? for letter in comb(s[i+1:], k - 1):
??????????? subseq += [s[i] + ' ' + letter]

??? return subseq

N = 3 # 輸入數(shù)據(jù)n
i = 1
seq = []
while i <= N: # 把所有元素列出來
??? seq.append(str(i))
??? seq.append(str(-i))
??? i += 1


s = comb(seq, N)
cseq = []
for i in range(len(s)): # 用循環(huán)實現(xiàn)組合，避免不同方向的同一基因進入同一個組合
??? temp = s[i].split(' ')
??? temp.remove('')
??? j = 1
??? flag = 0
??? n = []
??? n.append(abs(int(temp[0])))
??? while j < len(temp):
???? ???if abs(int(temp[j])) in n:
??????????? flag = 1
??????????? break
??????? else:
??????????? n.append(abs(int(temp[j])))
??????? j += 1
??? if flag == 0:
??????? cseq.append(temp)
num = 0
i = 0
while i < len(cseq): # 分別對每一個組合進行全排列
??? perm(cseq[i], 0, len(cseq[i]))
??? i += 1

print(num)