分割数字的算法

Question

给定一个正整数X,如何将它分成几个N部分,每个部分之间A和B哪里A <= B也是正整数？就是写

X = X_1 + X_2 + ... + X_N

哪里A <= X_i <= B和X_is 的顺序无关紧要？

Answer 1

如果您想知道执行此操作的方法的数量,那么您可以使用生成函数.

基本上,您对整数分区感兴趣.整数分区X是一种写入X正整数之和的方法.我们p(n)是整数分区的数量n.例如,如果n=5那么p(n)=7对应于分区:

5
4,1
3,2
3,1,1
2,2,1
2,1,1,1
1,1,1,1,1

生成函数p(n)是

sum_{n >= 0} p(n) z^n = Prod_{i >= 1} ( 1 / (1 - z^i) )

这对你有什么用？通过扩大右侧和取得系数,z^n你可以恢复p(n).不要担心产品是无限的,因为你只需要有限的许多项来计算p(n).事实上,如果这就是你想要的,那么就截断产品并停下来i=n.

为什么这样做？记住这一点

1 / (1 - z^i) = 1 + z^i + z^{2i} + z^{3i} + ...

因此系数z^n是写入方式的数量

n = 1*a_1 + 2*a_2 + 3*a_3 + ......

我现在想的a_i是i,分区中出现的次数n.

这是如何概括的？事实证明很容易.从上面的描述中,如果您只希望分区的各个部分位于给定的集合中A,那么不要i >= 1仅仅使用产品而不是产品i in A.让p_A(n)是整数分区的数量n,其零部件来自集A.然后

sum_{n >= 0} p_A(n) z^n = Prod_{i in A} ( 1 / (1 - z^i) )

再次,采用z^n此扩展中的系数可以解决您的问题.但我们可以进一步跟踪分区的部分数量.为此,请添加另一个占位符q以跟踪我们正在使用的部件数量.让p_A(n,k)是整数分区的数量n成k,其中部分来自部件集A.然后

sum_{n >= 0} sum_{k >= 0} p_A(n,k) q^k z^n = Prod_{i in A} ( 1 / (1 - q*z^i) )

因此服用的系数q^k z^n给出的整数的分区的数目n成k所在部位来自该组份A.

你怎么能这样编码？生成函数方法实际上为您提供了生成问题的所有解决方案的算法,以及从解决方案集中均匀采样的方法.一旦n与k被选择,在右边的产品是有限的.

Answer 2

这是这个问题的 python 解决方案，这还没有优化，但我试图让它尽可能简单，以演示解决这个问题的迭代方法。

此方法的结果通常是最大值和最小值的列表，中间可能有 1 或 2 个值。因此，这里有一个轻微的优化（使用abs），这将防止迭代器不断尝试找到从最大值倒数的最小值，反之亦然。

有一些递归方法可以做到这一点，看起来更加优雅，但这将完成工作，并希望为您提供更好的解决方案。

脚本：

# iterative approach in-case the number of partitians is particularly large
def splitter(value, partitians, min_range, max_range, part_values):
    # lower bound used to determine if the solution is within reach
    lower_bound = 0
    # upper bound used to determine if the solution is within reach
    upper_bound = 0
    # upper_range used as upper limit for the iterator
    upper_range = 0
    # lower range used as lower limit for the iterator
    lower_range = 0
    # interval will be + or -
    interval = 0

    while value > 0:
        partitians -= 1
        lower_bound = min_range*(partitians)
        upper_bound = max_range*(partitians)
        # if the value is more likely at the upper bound start from there
        if abs(lower_bound - value) < abs(upper_bound - value):
            upper_range = max_range
            lower_range = min_range-1
            interval = -1
        # if the value is more likely at the lower bound start from there
        else:
            upper_range = min_range
            lower_range = max_range+1
            interval = 1

        for i in range(upper_range, lower_range, interval):
            # make sure what we are doing won't break solution
            if lower_bound <= value-i and upper_bound >= value-i:
                part_values.append(i)
                value -= i
                break

    return part_values


def partitioner(value, partitians, min_range, max_range):
    if min_range*partitians <= value and max_range*partitians >= value:
        return splitter(value, partitians, min_range, max_range, [])
    else:
        print ("this is impossible to solve")

def main():
    print(partitioner(9800, 1000, 2, 100))

这个脚本背后的基本思想是，值需要落在 和 之间min*parts，max*parts对于解决方案的每一步，如果我们总是实现这个目标，我们最终将得到min < value < maxfor parts == 1，所以如果我们不断地从值中减去，并保持如果可能的话，在这个min < value < max范围内我们总会找到结果。

对于此代码的示例，它基本上总是会取走 或max，具体取决于更接近min哪个边界，直到留下一些非或值作为余数。valueminmax