多元线性方程整数解的计数

[TOC]

问题描述

统计

的非负整数解的个数。列出这些解。

枚举

静态地看，的范围容易确定，。各个范围的笛卡尔积是答案的范围，其中的元素记为。将每个带入方程验证，即可筛选出解。

from itertools import product
def cc(s, a):
    def p(x):
        return sum([x * a for x, a in zip(x, a)])
    
    return [x for x in product(*[range(s // ai + 1) for ai in a]) if p(x) == s]

递归

如果将决定中每个看作一个动态的过程，则已决定的对未决定的的范围有影响。我们可以沿着两个方向减小问题的规模，分别是

• 减小变量的个数
• 减小

def cr(s, a):
    def r(s, a, x):
        if s == 0:
            xs.append(tuple(x))
        elif s > 0 and len(a) != 0:
            x = list(x)
            r(s, a[:-1], x)        # 减小变量个数
            
            x = list(x)
            x[len(a) - 1] += 1
            r(s - a[-1], a, x)     # 减小S
    
    xs = []
    r(s, a, [0] * len(a))
    return xs

代码中x就是中的某个.

对比

将递归树叶子节点的个数作为递归的复杂度，与枚举法的中元素个数做对比，发现枚举空间的大小大约是递归空间大小的40倍。运行时间的比值也接近40。

附录

jupyter notebook 完整实验代码：

from itertools import *

l = 0

def cc(s, a):
    global l
    def p(x):
        return sum([x * a for x, a in zip(x, a)])
    
    l = len([x for x in product(*[range(s // ai + 1) for ai in a])])
    return [x for x in product(*[range(s // ai + 1) for ai in a]) if p(x) == s]

x1 = cc(100, [1, 5, 10, 25, 50])

cnt = 0

def cr(s, a):
    
    def r(s, a, x):
        global cnt
        if s == 0:
            xs.append(tuple(x))
            cnt += 1
        elif s > 0 and len(a) != 0:
            x = list(x)
            r(s, a[:-1], x)
            
            x = list(x)
            x[len(a) - 1] += 1
            r(s - a[-1], a, x)
        else:
            cnt += 1
    
    xs = []
    r(s, a, [0] * len(a))
    return xs

x2 = cr(100, [1, 5, 10, 25, 50])

set(x1) == set(x2)

x1 == x2

l / cnt

%timeit cc(100, [1, 5, 10, 25, 50])

%timeit cr(100, [1, 5, 10, 25, 50])