拒绝懒惰的家

需求:

给定一个数N,求出由序列[1..N]取出M个数的方法.

讨论:

求组合数有很多中算法,我认为最方便的就是二进制算法,算法的原理依据二项式定理,N的全组合数目为2^n-1.我们可以使用这个数的二进制形式来获得N的全组合.

Python实现:

def main(n,m=0):
    max = 2**n-1
    def makeResult(num):
        i=1;
        ret=[]
        while num > 0:
            if num & 1:
                ret.append(i)
            num>>=1
            i+=1
        return ret
    while max > 0:
        out=makeResult(max)
        if m!=0:
            if len(out)==m:
                print out
        else:
            print out
        max-=1
if __name__ == '__main__':
    main(5,3)

其中,max为2^n-1,我们让它递减至0,然后获得二进制中为1的位,并输出该位的位置,即获得的组合数.main的第二个参数是标志位,如果是0,求出全组合,如果不是0,取出特定个数的组合.