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

題目：

枚舉基因排列順序（Enumerating Gene Orders）

Given: A positive integer n<7.

所給：一個小于7的正整數(shù)n。

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

需得：n個數(shù)全排列的總數(shù)和所有排列方式（以任意順序給出）。

?

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

3

測試輸出

6

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

?

背景

基因組的重排（rearrangement）可以導(dǎo)致巨大變異的發(fā)生，因此很少對物種內(nèi)基因組產(chǎn)生作用。進化關(guān)系較近的物種通常具有相似的基因組結(jié)構(gòu)，因此在研究中，研究者往往將物種間相似的部分序列劃為同步塊（synteny blocks），物種間由于重排現(xiàn)象，synteny blocks往往分布到不同染色體的不同位置。我們用數(shù)字簡化表示每個synteny block，研究其排列，進而研究基因組的變化。

?

思路

假設(shè)數(shù)組含有n個元素，則提取數(shù)組中的每一個元素做一次頭元素，然后全排列除數(shù)組中除第一個元素之外的所有元素，這樣就達到了對數(shù)組中所有元素進行全排列的得目的。

(1) n個元素的全排列=（n-1個元素的全排列）+（另一個元素作為前綴）；

(2) 出口：如果只有一個元素的全排列，則說明已經(jīng)排完，則輸出數(shù)組；

(3) 不斷將每個元素放作第一個元素，然后將這個元素作為前綴，并將其余元素繼續(xù)全排列，直到出口，出口輸出后還需要還原數(shù)組。

用一個全局變量統(tǒng)計排列的總數(shù)。

?

Python知識點

排列是從n個元素中任取m個元素，并按照一定的順序進行排列。當(dāng)n==m時，稱為全排列。

全排列可以看做固定前i位，對第i+1位之后的再進行全排列，比如固定第一位，后面跟著n-1位的全排列，解決n-1位元素的全排列就能解決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]

?

num = 0

seq = ['1', '2', '3']

perm(seq, 0, len(seq))

print(num)