【ROSALIND】【练Python，学生信】 27 部分排列

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

题目：

部分排列（Partial Permutations）

Given: Positive integers n and k such that 100≥n>0 and 10≥k>0.

所给：两个正整数n和k，其中100≥n>0，10≥k>0。

Return: The total number of partial permutations P(n,k), modulo 1,000,000.

需得：由n，k所得部分排列的组合数的模。

测试数据

21 7

测试输出

51200

生物学背景

亲缘关系相近的物种通常共有某些基因，我们通过比较这些基因能够对导致改变的基因重排现象进行研究。但不同的基因组并不遵照同样的方式进化，必然会产生不同的基因，因此我们需要用改进之前的全排列方式，考虑只有部分基因参与排列的情况。

数学背景

对排列的介绍请参考19 枚举基因排列顺序。

假设总体共有n个数据，对于部分排列，我们只需要考虑其中k个数据的排列（k≤n），用P(n,k)表示排列总数。当然，k=n时，问题又变成了n个数据的全排列，即P(n,n)=n！。

思路

从n个数中取k个数进行排列。

代码

def factorial(n):
    """计算阶乘的函数"""
    fac = 1
    i = n
    while i > 1:
        fac = fac * i
        i -= 1
    return  fac

n = 21
k = 7

fac = factorial(n) / factorial(n - k) # 从n中选k个数进行排列
result = fac % 1000000 # 取模
print(result)