【Rosalind】Enumerating Oriented Gene Orderings – 排列与组合

最近更新比较少,做题也比较慢,因为手头事情多起来了,而且这些题目真是很难了,不静下来在纸上算一会我是真写不出来。今天就分享一道和之前两道题有关的一道习题吧。

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

Sample Output

思路

这道题和之前的一道题非常类似,首先要生成全排列,然后需要对每个位置的正负进行组合。

首先收集(1,2,...,n)的全排列到一个列表里。

然后从(1,-1)这两个元素中随机选n次,得到的所有组合放到一个列表里。

假如n=3,全排列表里应该有个(1,2,3),符号的组合里应该有一个(1,-1,1),我们再把这两个列表里的列表或元组对应相乘,前面这个例子输出就应该是(1,-2,3)

全排列的数量是n!,符号组合的数目是2^n,所以总的输出的可能数应该是n!*(2**n)

我的代码

其中,全排列部分我是用上次写的dfs算法写的,然后把结果输出到了中间文件里。符号组合的函数我是用itertools里的product函数完成的。

参考

  1. https://emmettoncloud.cn/archives/50

  2. https://emmettoncloud.cn/archives/55

Share this page if you like this post:)