求两个线性等式为tru的整数集合

Question

我可以用什么算法来找到n1, n2, ... ,n7的所有正整数值的集合，其中下面的不等式成立。在

97n1 + 89n2 + 42n3 + 20n4 + 16n5 + 11n6 + 2n7 - 185 > 0
-98n1 - 90n2 - 43n3 - 21n4 - 17n5 - 12n6 - 3n7 + 205 > 0
n1 >= 0, n2 >= 0, n3 >=0. n4 >=0, n5 >=0, n6 >=0, n7 >= 0

例如，一个集合n1= 2, n2 = n3 = ... = n7 =0使不等式成立。如何找出所有其他的值集？类似的问题已经在M.SE上发布。在

添加了：：我需要对n个变量（可能很大）的解进行推广。我可以申请什么程序？对于另一个特殊情况n=8

^{pr2}$

Python需要永远。Wolfram Mathematica表明在不到一分钟内有{}溶液。在

Length[Solve[{97 n1 + 89 n2 + 42 n3 + 20 n4 + 16 n5 + 11 n6 + 6 n7 + 
     2 n8 - 185 > 0, 
   -98 n1 - 90 n2 - 43 n3 - 21 n4 - 17 n5 - 12 n6 - 7 n7 - 3 n8 + 
     205 > 0,
   n1 >= 0, n2 >= 0, n3 >= 0, n4 >= 0, n5 >= 0, n6 >= 0, n7 >= 0, 
   n8 >= 0}, {n1, n2, n3, n4, n5, n6, n7, n8}, Integers]]

Answer 1

有1013种解决方案，但我不知道最有效的解决方法。在

看看第二个不等式，17 * n5不能大于205（否则整个左手边不可能是正的）。这将导致n5 <= 12。通过为每个其他变量计算一个相似的界限，您可以将问题简化为可以使用嵌套循环快速解决的问题。在

这个Java代码打印出所有的解决方案。在

for (int n1 = 0; n1 <= 2; n1++) {
    for (int n2 = 0; n2 <= 2; n2++) {
        for (int n3 = 0; n3 <= 4; n3++) {
            for (int n4 = 0; n4 <= 9; n4++) {
                for (int n5 = 0; n5 <= 12; n5++) {
                    for (int n6 = 0; n6 <= 17; n6++) {
                        for (int n7 = 0; n7 <= 68; n7++) {
                            if (97 * n1 + 89 * n2 + 42 * n3 + 20 * n4 + 16 * n5 + 11 * n6 + 2 * n7 - 185 > 0
                                && -98 * n1 - 90 * n2 - 43 * n3 - 21 * n4 - 17 * n5 - 12 * n6 - 3 * n7 + 205 > 0) {
                                System.out.println(Arrays.asList(n1, n2, n3, n4, n5, n6, n7));
                            }
                        }
                    }
                }
            }
        }
    }
}

通过在

^{pr2}$

达到205。在

例如，n4循环可以替换为

for (int n4 = 0; 98 * n1 + 90 * n2 + 43 * n3 + 21 * n4 < 205; n4++)

如果你以这种方式改变所有7个循环，所有1013个解决方案都可以很快找到。在

Answer 2

在你给我的两个例子中，我注意到了相同的模式。例如，对于第一种情况，如果你把这两个方程加在一起，你会得到

-n1 - n2 - n3 - n4 - n5 - n6 - n7 + 20 > 0

可以重新排列为

^{pr2}$

这是一个很好的有界方程，你可以用蛮力。具体地说，你可以迭代从0到19的n1，从0到19-n1等等。一个可能的解决方案是（0，0，0，0，0，0，0），但是我们注意到这并不满足我们原来的方程。所以，只需生成（n1，n2，…，n7）的所有可能值，只保留那些满足方程的值。将所有这些结果硬编码到

def find_solutions(N):
    sols = []
    for n1 in xrange(N):
        for n2 in xrange(N-n1):
            for n3 in xrange(N-n1-n2):
                for n4 in xrange(N-n1-n2-n3):
                    for n5 in xrange(N-n1-n2-n3-n4):
                        for n6 in xrange(N-n1-n2-n3-n4-n5):
                            for n7 in xrange(N-n1-n2-n3-n4-n5-n6):
                                if (97*n1 + 89*n2 + 42*n3 + 20*n4 + 16*n5 + 11*n6 + 2*n7 - 185 > 0 and
                                    -98*n1 - 90*n2 - 43*n3 - 21*n4 - 17*n5 - 12*n6 - 3*n7 + 205 > 0):
                                    sols.append((n1, n2, n3, n4, n5, n6, n7))
return sols

find_solutions(20)在0.6秒内找到所有1013个解。同样，对于第二种情况，它在2.3秒内找到所有4015个解。现在，这一点很难概括，但它表明，使用一种聪明的方法，Python或任何其他语言都不必慢。在

另一方面，递归允许我们将其推广到任意数量的嵌套循环中，但代价是运行速度稍慢。在

def find_solutions(N, coeffs, depth=0, variables=None, subtotal=None, solutions=None):
    if variables is None:
        solutions = []
        subtotal = [0 for _ in xrange(len(coeffs[0]))]
        variables = [0 for _ in xrange(len(coeffs[0])-1)]
    if depth == len(coeffs[0])-2:
        for v in xrange(N-sum(variables[:depth])):
            conditions = all(
                subtotal[i]+coeffs[i][depth]*v > coeffs[i][-1]
                for i in xrange(len(coeffs))
            )
            if conditions:
                variables[depth] = v
                solutions.append(tuple(variables))
    else:
        for v in xrange(N-sum(variables[:depth])):
            variables[depth] = v
            total = [subtotal[i]+coeffs[i][depth]*v for i in xrange(len(coeffs))]
            find_solutions(N, coeffs, depth+1, variables, total, solutions)
    if depth == 0:
        return solutions

要运行此操作，请生成每个方程的系数并将其传递给函数。记住常数的符号是颠倒的！在

coeffs = [
    [97, 89, 42, 20, 16, 11, 2, 185],
    [-98, -90, -43, -21, -17, -12, -3, -205]
]
solutions = find_solutions(20, coeffs)
print(len(solutions))

这一个在1.6秒内完成n=7个案例，5.8秒完成n=8案例。如果你希望你的n变得非常大，我会考虑任何可能的优化，但目前看来这是令人满意的。在

剩下的问题是方程的和是否总是简化为n1 + n2 + ... nn < N。如果不是这样的话，有一个简单的解决方案可以解决这个问题，但是我不想过早地过度概括您提供的示例之外的代码。在

最后，我设想同样的方法可以用Java或C实现，而且可能会更快。如果你的一般案件需要更长时间才能解决，我不介意这样做。在

Answer 3

Reti43的想法是正确的，但是有一个快速递归的解决方案，它可以在对不等式的限制较少的假设下工作。在

def solve(smin, smax, coef1, coef2):
    """
    Return a list of lists of non-negative integers `n` that satisfy
    the inequalities,

    sum([coef1[i] * n[i] for i in range(len(coef1)]) > smin
    sum([coef2[i] * n[i] for i in range(len(coef1)]) < smax

    where coef1 and coef2 are equal-length lists of positive integers.
    """
    if smax < 0:
        return []

    n_max = ((smax-1) // coef2[0])
    solutions = []
    if len(coef1) > 1:
        for n0 in range(n_max + 1):
            for solution in solve(smin - n0 * coef1[0],
                                  smax - n0 * coef2[0], 
                                  coef1[1:], coef2[1:]):
                solutions.append([n0] + solution)
    else:
        n_min = max(0, (smin // coef1[0]) + 1)
        for n0 in range(n_min, n_max + 1):
            if n0 * coef1[0] > smin and n0 * coef2[0] < smax:
                solutions.append([n0])
    return solutions

你可以把这个应用到你原来的问题上

^{pr2}$

对于这样一个长期的问题

smin, coef1 = 185, (97, 89, 42, 20, 16, 11, 6, 2)
smax, coef2 = 205, (98, 90, 43, 21, 17, 12, 7, 3)
solns8 = solve(smin, smax, coef1, coef2)
len(solns8)
4015

在我的Macbook上，这两个问题都在毫秒内解决。对于稍微大一点的问题，这应该是合理的，但从根本上说，它在系数N的数量中是O（2^N）。它实际扩展的程度取决于附加系数的大小-系数越大（与smax smin相比），可能的解越少，运行得越快。在

更新了：从关于链接的M.SE post的讨论中，我看到这两个不等式之间的关系是问题结构的一部分。鉴于此，可以给出一个稍微简单的解决方案。下面的代码还包括一些额外的优化，在我的笔记本电脑上，将8变量情况下的解决方案从88毫秒加速到34毫秒。我已经在22个变量的例子中尝试了这个方法，在不到一分钟的时间内就得到了结果，但是对于成百上千的变量来说，这是不可能的。在

def solve(smin, smax, coef):
    """
    Return a list of lists of non-negative integers `n` that satisfy
    the inequalities,

    sum([coef[i] * n[i] for i in range(len(coef)]) > smin
    sum([(coef[i]+1) * n[i] for i in range(len(coef)]) < smax

    where coef is a list of positive integer coefficients, ordered
    from highest to lowest.
    """
    if smax <= smin:
        return []
    if smin < 0 and smax <= coef[-1]+1:
        return [[0] * len(coef)]

    c0 = coef[0]
    c1 = c0 + 1
    n_max = ((smax-1) // c1)
    solutions = []
    if len(coef) > 1:
        for n0 in range(n_max + 1):
            for solution in solve(smin - n0 * c0,
                                  smax - n0 * c1, 
                                  coef[1:]):
                solutions.append([n0] + solution)
    else:
        n_min = max(0, (smin // c0) + 1)
        for n0 in range(n_min, n_max + 1):
            solutions.append([n0])
    return solutions

你可以把它应用到像这样的8变量例子中

solutions = solve(185, 205, (97, 89, 42, 20, 16, 11, 6, 2))
len(solutions)
4015

此解直接枚举有界区域中的点阵点。因为你想要所有这些解，得到它们所需的时间将与（至多）束缚晶格点的数量成比例（最多），而束缚晶格点的数量随维度（变量）的数量呈指数增长。在