n位二进制中m个1的所有组合个数

Posted on | In |

用递归和动态规划：

将n个元素从左往右排好序。每次选择的m个元素的组合按如下步骤，

  • 先选第一个元素，有n-m+1种选择方案
  • 第一个元素的位置确定后，其余待选择的m-1个元素从已选择元素的右边选择。这是个与原问题同构的子问题，可以用递归。
  • 递归的终止条件有两个，一个是n==m也就是剩余元素数量和剩余位置数量相等，只有一种组合方法；一个是m==0也就是m个元素都已经排完了。
  • 用一个全局的数据结构存储动态规划的子问题状态，避免重复计算。

而根据第一个元素的位置生成的n-m+1个子问题是互斥且完备的，因此方法成立。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def combination(n, m):
    def recur(n, m, states):
        if n == m or m == 0:
            return 1
        else:
            res = 0
            for i in range(1, n-m+2):
                if (n-i, m-1) not in  states:
                    num = recur(n-i, m-1, states)
                    states[(n-i, m-1)] = num
                    res += num
                else:
                    res += states[(n-i, m-1)]
            return res
    states = {}
    if (m == 0 and n == 0) or m > n or m < 0 or n < 0:
        return 0
    else:
        return recur(n,m, states)

带入参数计算combination(1000, 500)得到一个很大的组合数数：

1
2
3
4
2702882409454365695156146936259752754961520084465482870073928751066254287055
2219389861248392450237016536260608502154610480220975005067991754989421969951
8475423665484263751733356162464079737887344364574161119497604571044985756287
880514600994219426752366915856603136862602484428109296905863799821216320