最近更新比较少，做题也比较慢，因为手头事情多起来了，而且这些题目真是很难了，不静下来在纸上算一会我是真写不出来。今天就分享一道和之前两道题有关的一道习题吧。
Problem
A signed permutation of length nn is some ordering of the positive integers {1,2,…,n} in which each integer is then provided with either a positive or negative sign (for the sake of simplicity, we omit the positive sign). For example, π=(5,−3,−2,1,4) is a signed permutation of length 5.
Given: A positive integer n≤6.
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).
Sample Dataset
|
1 |
2 |
Sample Output
|
1 2 3 4 5 6 7 8 9 |
8 -1 -2 -1 2 1 -2 1 2 -2 -1 -2 1 2 -1 2 1 |
思路
这道题和之前的一道题非常类似，首先要生成全排列，然后需要对每个位置的正负进行组合。
首先收集(1,2,...,n)的全排列到一个列表里。
然后从(1,-1)这两个元素中随机选n次，得到的所有组合放到一个列表里。
假如n=3，全排列表里应该有个(1,2,3)，符号的组合里应该有一个(1,-1,1)，我们再把这两个列表里的列表或元组对应相乘，前面这个例子输出就应该是(1,-2,3)。
全排列的数量是n!，符号组合的数目是2^n，所以总的输出的可能数应该是n!*(2**n)。
我的代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
""" Rosalind Problems: Enumerating Oriented Gene Orderings Problem ID: SIGN http://rosalind.info/problems/sign/ A signed permutation of length n is some ordering of the positive integers {1,2,…,n} in which each integer is then provided with either a positive or negative sign (for the sake of simplicity, we omit the positive sign). For example, π=(5,−3,−2,1,4) is a signed permutation of length 5. Given: A positive integer n≤6. 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). """ from itertools import product def fac(x): if x==1: return x else: return x*fac(x-1) def perm(n): elem = [] visit = [] for i in range(1,n+1,1): elem.append(i) visit.append(True) #print(elem) temp = [0*n for i in range(len(elem))] def dfs(pos): if pos == len(elem): f = open('perm.txt','a+') for i in temp: f.write(str(i)+' ') f.write('\n') f.close() return for x in range(len(elem)): if visit[x] == True: temp[pos] = elem[x] visit[x] = False dfs(pos+1) visit[x] = True dfs(0) f = open('perm.txt', 'r') data = f.readlines() f.close() data2 = [] for lines in data: data2.append(lines.replace(' \n', '')) allperm = [] for i in range(fac(n)): allperm.append([]) #print(allperm) for i in range(len(data2)): for num in data2[i]: if num != ' ': allperm[i].append(int(num)) #print(allperm) return allperm def signed(alist): num = len(alist) ctrl = [] neg_pos = product([1,-1],repeat=num) for i in neg_pos: ctrl.append(i) #print(ctrl) combination = [[] for i in range(2**num)] for i in ctrl: ind = ctrl.index(i) for x in alist: pos = alist.index(x) combination[ind].append(i[pos]*x) #print(combination) for i in combination: for j in i: if i.index(j) != num-1: print(j, end=' ') else: print(j, end='\n') def main(): #Given number N = 5 permutations = perm(N) #signed([1,2,3]) print(fac(N)*(2**N)) for i in permutations: signed(i) if __name__ == '__main__': main() |
其中，全排列部分我是用上次写的dfs算法写的，然后把结果输出到了中间文件里。符号组合的函数我是用itertools里的product函数完成的。
![[Python for Bioinformatics 2学习笔记]5.1 Handling files: Reading files](https://emmettoncloud.cn/wp-content/themes/boxcard/img/thumb-medium.png)