numb的分区生成算法

Question

我的目标是将给定数S的所有分区按预定义值进行分解，使之和小于S且大于0.8S。 例如，S=1000，我们要将1000分解为17x+20y+150z类型的和，因此17x+20y+150z小于1000，大于800。你知道吗

我遇到了一个类似的问题，但是我很难理解如何将值存储到数组中。你知道吗

Answer 1

据我所知，您不希望生成S的实际分区，因为这样做没有意义：

For example, S = 1000, and we want to decompose 1000 into a sum of type 17x + 20y + 150z, so that 17x + 20y + 150z is less than 1000

如果它小于1000，它就不是1000的分区。你知道吗

所以我假设您想生成从0.8S到S的所有数字的分区。你知道吗

I've come across a solution of a similar problem, but I am having trouble understanding how can I store the values into an array.

只要做list(partitions(n))。对于您的问题：

[list(partitions(i)) for i in range(int(0.8*S), S)]

其中partitions是您链接到的函数，由David Eppstein发布，我将复制到下面：

def partitions(n):
    # base case of recursion: zero is the sum of the empty list
    if n == 0:
        yield []
        return

    # modify partitions of n-1 to form partitions of n
    for p in partitions(n-1):
        yield [1] + p
        if p and (len(p) < 2 or p[1] > p[0]):
            yield [p[0] + 1] + p[1:]

Answer 2

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

在这里，我找到适合您的模式的数字，范围是990到1000（包括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是最小的整数。但是，这有时会产生非正值（当sy>；=lo）；当出现这种情况时，max函数确保1是分配给x的最小值。你知道吗

---

在看到约翰科尔曼的更普遍的解决方案后，我也受到启发写了一个。我的并不像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)

Answer 3

这里是一种递归方法，给定一个下限a，一个上限b，和一个系数列表nums，返回一个非负整数向量列表，当与相应的系数相乘然后求和时，返回一个介于a和b之间的和。函数允许0作为值。但请注意，例如，整数解(x,y,z)与x,y,z >= 1和(x,y,z)之间有一个简单的一一对应关系

990 <= 17x + 20y + 150z <= 1000

溶液(x,y,z)与x,y,z >= 0和

990 - 187 <= 17x + 20y + 150z <= 1000 - 187

代码如下：

import math

def allSolutions(a,b,nums):
    if len(nums) == 0:
        return []

    c = nums[0]
    m = max(0,math.ceil(a/c))
    M = math.floor(b/c)

    if len(nums) == 1:
        return [(x,) for x in range(m,M+1)]

    solutions = []
    for x in range(M+1):
        solutions.extend((x,)+s for s in allSolutions(a-c*x,b-c*x,nums[1:]))
    return solutions

例如，allSolutions(990-187,1000-187,[17,20,150])产生的86种解决方案基本上与他们在优秀答案中发现的@PM2Ring相同。allSolutions(800-187,1000-187,[17,20,150])也找到了1284个解决方案。你知道吗