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

題目：

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

Given: A positive integer n<7.

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

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

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

?

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

3

測(cè)試輸出

6

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

?

背景

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

?

思路

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

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

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

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

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

?

Python知識(shí)點(diǎn)

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

全排列可以看做固定前i位，對(duì)第i+1位之后的再進(jìn)行全排列，比如固定第一位，后面跟著n-1位的全排列，解決n-1位元素的全排列就能解決n位元素的全排列。

?

代碼

def perm(seq, begin, end):

'''進(jìn)行排列的函數(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)