【ROSALIND】【练Python，学生信】43 计算子集数目

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

题目：

计算子集数目（Counting Subsets）

Given: A positive integer n (n≤1000).

所给：一个正整数n（n不大于1000）。

Return: The total number of subsets of {1,2,…,n} modulo 1,000,000.

需得：集合{1,2,…,n}的所有子集数目，结果取模。

测试数据

3

测试输出

8

生物学背景

        特征（character）是生物基因或表型上的特性，可以依据一个特征把一群同类生物划分为两个亚群。单核苷酸多态性（SNP）是一种常用的基因特征，主要是指在基因组水平上由单个核苷酸的变异所引起的DNA序列多态性。利用人类SNP可以研究基因组的迁徙、融合及进化现象。

        我们可以把一组特征想象为一个集合，可以用某个特征是否存在来描述生物体。这样一个生物体具有的特征就是这个集合的一个子集。

数学背景

        集合是数学中的基本概念。集合包含的每个对象称为集合的元素。举例来说，{the moon, the sun, Wilford Brimley}是一个集合，the moon是集合的一个元素。集合元素不分顺序，只要元素相等就是同一个集合，即{the moon, the sun, Wilford Brimley}等价于{Wilford Brimley, the moon, the sun}。集合中元素不可重复。

        如果集合A是集合B的子集（A⊆B），则集合A中的每一个元素都是B的元素。例如{the sun, the moon}⊆{the sun, the moon, Wilford Brimley}。需要注意的是，空集∅是任何集合的子集。

        组合是指从n个不同元素中取出m个不同元素（0≤m≤n），不管其顺序合成一组，称为从n个元素中不重复地选取m个元素的一个组合。

思路

        本题较简单，实质是计算组合总数。直接套用组合的公式，算组合数即可。可以直接用Python定义好的阶乘函数，自己写的话也很简单。不要忘了空集也是子集。

代码

def myfactorial(n, m):
    """自己定义一个可以算阶乘的函数，计算n(n-1)(n-2)…(n-m)"""

    sum = 1
    i = n
    while i >= m:
        sum *= i
        i -= 1

    return sum


n = 3
result = 1 # 将空集先加入结果
for i in range(1,n + 1): # 利用循环结算组合总数
    tep = myfactorial(n, n-i+1)/myfactorial(i,1) # 套用组合公式
    result += tep

print(int(result % 1000000))