python - 生成数字分区的算法

Question

我的目标是通过预定义值分解给定数字 S 的所有分区，以便总和小于 S 且大于 0.8S。比如S=1000，我们要把1000分解成17x+20y+150z类型的和，这样17x+20y+150z就是小于1000大于800。

我遇到了一个 solution一个类似的问题，但我无法理解如何将值存储到数组中。

Answer 1

这里不需要完整的分区算法。您可以通过简单的循环找到您想要的数字。如果您有固定数量的系数，如问题中给出的那样，那么您可以只使用几个 for 循环。如果系数的数量可以变化，那么您将需要更复杂的解决方案。

我在这里找到适合您的模式的数字，范围在 990 到 1000(含)之间，以使输出易于管理，因为在 800 到 1000 的范围内有 1284 种 x、y 和 z 的组合。

我假设您想对这些解决方案做一些事情，所以我将它们保存在一个列表中以供进一步处理。

from itertools import count

mx, my, mz = 17, 20, 150
lo = 990
hi = 1000

solns = []
for z in count(1):
    sz = z * mz
    if sz > hi:
        break
    for y in count(1):
        sy = sz + y * my
        if sy > hi:
            break
        d = lo - sy
        x = max(1, -(-d // mx))
        for x in count(x):
            s = sy + x * mx
            if s > hi:
                break
            t = (z, y, x, s)
            solns.append(t)

print(len(solns))
for t in solns:
    print(t)

输出

86
(1, 3, 46, 992)
(1, 4, 45, 995)
(1, 5, 44, 998)
(1, 8, 40, 990)
(1, 9, 39, 993)
(1, 10, 38, 996)
(1, 11, 37, 999)
(1, 14, 33, 991)
(1, 15, 32, 994)
(1, 16, 31, 997)
(1, 17, 30, 1000)
(1, 20, 26, 992)
(1, 21, 25, 995)
(1, 22, 24, 998)
(1, 25, 20, 990)
(1, 26, 19, 993)
(1, 27, 18, 996)
(1, 28, 17, 999)
(1, 31, 13, 991)
(1, 32, 12, 994)
(1, 33, 11, 997)
(1, 34, 10, 1000)
(1, 37, 6, 992)
(1, 38, 5, 995)
(1, 39, 4, 998)
(2, 1, 40, 1000)
(2, 4, 36, 992)
(2, 5, 35, 995)
(2, 6, 34, 998)
(2, 9, 30, 990)
(2, 10, 29, 993)
(2, 11, 28, 996)
(2, 12, 27, 999)
(2, 15, 23, 991)
(2, 16, 22, 994)
(2, 17, 21, 997)
(2, 18, 20, 1000)
(2, 21, 16, 992)
(2, 22, 15, 995)
(2, 23, 14, 998)
(2, 26, 10, 990)
(2, 27, 9, 993)
(2, 28, 8, 996)
(2, 29, 7, 999)
(2, 32, 3, 991)
(2, 33, 2, 994)
(2, 34, 1, 997)
(3, 1, 31, 997)
(3, 2, 30, 1000)
(3, 5, 26, 992)
(3, 6, 25, 995)
(3, 7, 24, 998)
(3, 10, 20, 990)
(3, 11, 19, 993)
(3, 12, 18, 996)
(3, 13, 17, 999)
(3, 16, 13, 991)
(3, 17, 12, 994)
(3, 18, 11, 997)
(3, 19, 10, 1000)
(3, 22, 6, 992)
(3, 23, 5, 995)
(3, 24, 4, 998)
(4, 1, 22, 994)
(4, 2, 21, 997)
(4, 3, 20, 1000)
(4, 6, 16, 992)
(4, 7, 15, 995)
(4, 8, 14, 998)
(4, 11, 10, 990)
(4, 12, 9, 993)
(4, 13, 8, 996)
(4, 14, 7, 999)
(4, 17, 3, 991)
(4, 18, 2, 994)
(4, 19, 1, 997)
(5, 1, 13, 991)
(5, 2, 12, 994)
(5, 3, 11, 997)
(5, 4, 10, 1000)
(5, 7, 6, 992)
(5, 8, 5, 995)
(5, 9, 4, 998)
(6, 2, 3, 991)
(6, 3, 2, 994)
(6, 4, 1, 997)

我想我应该解释一下这行有点神秘的代码:

x = max(1, -(-d // mx))

//为底除运算符，a//b返回小于等于a/b的最大整数。

因此 -d//mx 是最大的整数 <= -d/mx，并且 -(-d//mx)因此是最低整数 >= d/mx。但是，这有时会产生非正值(当 sy >= lo 时)；当发生这种情况时，max 函数确保 1 是分配给 x 的最低值。

---

在看到 John Coleman 的更通用的解决方案后，我受到启发也写了一个。我的不像 John 的那样简洁易读，但它使用迭代而不是递归，而且它使用的内存更少。它的速度也大约是原来的两倍，尽管它比我只能处理 3 个系数的原始版本慢了大约 20%。

这段代码不是返回一个列表，而是一个生成器。因此，您可以在生成结果时使用结果，也可以将结果收集到列表或其他集合中，例如列表的 dict，每个列表包含对应于给定总和的元组，总和作为该列表的键。

def linear_sum(lo, hi, coeff):
    ''' Find all positive integer solutions of the linear equation with 
        coefficients `coeff` with sum `s`: lo <= s <= hi 
    '''
    num = len(coeff)
    vector = [1] * num
    mx = coeff[-1]
    s = sum(coeff[:-1])
    while True:
        olds = s
        xlo = max(1, -((s - lo) // mx))
        xhi = 1 + (hi - s) // mx
        s += mx * xlo
        for vector[-1] in range(xlo, xhi):
            yield s, tuple(vector)
            s += mx

        # Increment next vector component
        k = num - 2
        vector[k] += 1
        s = olds + coeff[k]

        # If the component is too high 
        while s > hi:
            if not k:
                return

            # reset this component,
            s -= coeff[k] * (vector[k] - 1)
            vector[k] = 1

            # and increment the next component.
            k -= 1
            vector[k] += 1
            s += coeff[k]

# Tests

coeff = 150, 20, 17

# Create a list    
solns = [v for v in linear_sum(800, 1000, coeff)]
print(len(solns))

# Generate solutions one by one and verify that they give the correct sum
for s, vector in linear_sum(990, 1000, coeff):
    assert s == sum(u*v for u, v in zip(coeff, vector))
    print(s, vector)

输出

1284
992 (1, 3, 46)
995 (1, 4, 45)
998 (1, 5, 44)
990 (1, 8, 40)
993 (1, 9, 39)
996 (1, 10, 38)
999 (1, 11, 37)
991 (1, 14, 33)
994 (1, 15, 32)
997 (1, 16, 31)
1000 (1, 17, 30)
992 (1, 20, 26)
995 (1, 21, 25)
998 (1, 22, 24)
990 (1, 25, 20)
993 (1, 26, 19)
996 (1, 27, 18)
999 (1, 28, 17)
991 (1, 31, 13)
994 (1, 32, 12)
997 (1, 33, 11)
1000 (1, 34, 10)
992 (1, 37, 6)
995 (1, 38, 5)
998 (1, 39, 4)
1000 (2, 1, 40)
992 (2, 4, 36)
995 (2, 5, 35)
998 (2, 6, 34)
990 (2, 9, 30)
993 (2, 10, 29)
996 (2, 11, 28)
999 (2, 12, 27)
991 (2, 15, 23)
994 (2, 16, 22)
997 (2, 17, 21)
1000 (2, 18, 20)
992 (2, 21, 16)
995 (2, 22, 15)
998 (2, 23, 14)
990 (2, 26, 10)
993 (2, 27, 9)
996 (2, 28, 8)
999 (2, 29, 7)
991 (2, 32, 3)
994 (2, 33, 2)
997 (2, 34, 1)
997 (3, 1, 31)
1000 (3, 2, 30)
992 (3, 5, 26)
995 (3, 6, 25)
998 (3, 7, 24)
990 (3, 10, 20)
993 (3, 11, 19)
996 (3, 12, 18)
999 (3, 13, 17)
991 (3, 16, 13)
994 (3, 17, 12)
997 (3, 18, 11)
1000 (3, 19, 10)
992 (3, 22, 6)
995 (3, 23, 5)
998 (3, 24, 4)
994 (4, 1, 22)
997 (4, 2, 21)
1000 (4, 3, 20)
992 (4, 6, 16)
995 (4, 7, 15)
998 (4, 8, 14)
990 (4, 11, 10)
993 (4, 12, 9)
996 (4, 13, 8)
999 (4, 14, 7)
991 (4, 17, 3)
994 (4, 18, 2)
997 (4, 19, 1)
991 (5, 1, 13)
994 (5, 2, 12)
997 (5, 3, 11)
1000 (5, 4, 10)
992 (5, 7, 6)
995 (5, 8, 5)
998 (5, 9, 4)
991 (6, 2, 3)
994 (6, 3, 2)
997 (6, 4, 1)