【ROSALIND】【练Python，学生信】19 枚举基因排列顺序

如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面  谢谢配合~

题目：

枚举基因排列顺序（Enumerating Gene Orders）

Given: A positive integer n<7.

所给：一个小于7的正整数n。

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

需得：n个数全排列的总数和所有排列方式（以任意顺序给出）。

 

测试数据

3

测试输出

6

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

 

背景

基因组的重排（rearrangement）可以导致巨大变异的发生，因此很少对物种内基因组产生作用。进化关系较近的物种通常具有相似的基因组结构，因此在研究中，研究者往往将物种间相似的部分序列划为同步块（synteny blocks），物种间由于重排现象，synteny blocks往往分布到不同染色体的不同位置。我们用数字简化表示每个synteny block，研究其排列，进而研究基因组的变化。

 

思路

假设数组含有n个元素，则提取数组中的每一个元素做一次头元素，然后全排列除数组中除第一个元素之外的所有元素，这样就达到了对数组中所有元素进行全排列的得目的。

(1) n个元素的全排列=（n-1个元素的全排列）+（另一个元素作为前缀）；

(2) 出口：如果只有一个元素的全排列，则说明已经排完，则输出数组；

(3) 不断将每个元素放作第一个元素，然后将这个元素作为前缀，并将其余元素继续全排列，直到出口，出口输出后还需要还原数组。

用一个全局变量统计排列的总数。

 

Python知识点

排列是从n个元素中任取m个元素，并按照一定的顺序进行排列。当n==m时，称为全排列。

全排列可以看做固定前i位，对第i+1位之后的再进行全排列，比如固定第一位，后面跟着n-1位的全排列，解决n-1位元素的全排列就能解决n位元素的全排列。

 

代码

def perm(seq, begin, end):

'''进行排列的函数'''

    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)