【ROSALIND】【练Python，学生信】29 有方向的基因排列枚举

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

题目：

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

Given: A positive integer n≤6.

所给：一个不大于6的正整数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的数字组成的全排列（有正负符号）的数量，以及所有的排列方式（由任意顺序给出）。

测试数据

2

测试输出

8

-1 -2

-1 2

1 -2

1 2

-2 -1

-2 1

2 -1

2 1

生物学背景

        在之前的问题中，我们已经知道亲缘关系相近的物种往往也有相似的基因组，染色体通过其上基因的重排发生改变。我们也用排列的方式模拟了这种改变。然而在实际中，基因组是有方向的，很多时候转录只能沿一个方向进行。这样我们就需要在原先的排列模型中引入正负符号，从而代表基因的方向。

数学背景

        有符号的排列是在排列的基础上给每个元素加上正负号。

思路

        我把这道题看成两个部分：1）n个数字看成n个组，每组2个元素，分别为n和-n，每组抽取一个组合起来，这样我们就得到了2^n个组合。2）对每个组合再进行全排列，每个组合有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]

def comb(s, k):
    """辅助进行元素抽取的函数"""
    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 # 输入数据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)): # 用循环实现组合，避免不同方向的同一基因进入同一个组合
    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)