math - 查找按词汇顺序总和为给定数字的数千组的第 n 个出现

Question

上一个问题要求按词汇顺序（从最低到最高）解决

a+b+c+d… = x

其中 a,b,c,d... 是 0-999 之间的任意整数，x 是固定整数

给出了一个答案，它使用 python 有效地完全计算了这一点。

但是，对于非常大的数字，循环可能需要数年才能完成。

例如，巨大的数字：

304,153,525,784,175,759

是一个解决方案，x=2700因为三人一组加起来2700

304+153+525+784+175+759 = 2700

但是，要遍历算法以获得等于该数字的第 n^{个解决方案将需要数月或数年。}

有没有办法直接计算第n^个解？即对于一个已知的解决方案，计算有多少解决方案小于这个。

标签： mathnumberspartition

Answer 1

这是一种查找解决方案索引的方法（或：有多少较小的解决方案）。代码有两部分：

• n对于给定的 sum ，找出一些固定数量的组有多少解决方案x。这是一个递归函数。基本上，对于ngroups 和 sum ，对于从 0 到 999 的所有 k，用groups 和 sum 总结x有多少解决方案。由于递归函数经常使用相同的值调用，结果存储在一个记忆字典中，以便下次立即使用。n-1x-k

• 使用此函数计算存在多少较小的解决方案。这是一种类似的求和方式。例如，对于 6 组并以 开始304，计算有多少个 5 组在 之后开始303并求和x-303，将 5 组的数量相加以 开始302并求和x-302，等等。然后，以304,153开始，找出有多少 4-组开始后304,152和总和x-304-152等。

这是完整的代码，测试了相当多的输入（由前面的程序生成的测试）。给定的 18 位数字只需要几秒钟。

grouping = 3
max_in_group = 10 ** grouping - 1
number_to_test = 304153525784175759  # number_to_test = '304,153,525,784,175,759'
d = {}  # dictionary for memoization

# count how many solutions there are for n groups summing to x, and each group being a number from 0 to max_in_group;
# when counting simple digit sums, n is the number of digits, and max_in_group should be 9;
# when counting in groups of thousands, n is the number of groups (digits / 3), and max_in_group should be 999
def count_digitsums(x, n, max_in_group=9):
    if not(0 <= x <= n * max_in_group):
        return 0
    elif n == 1:
        return 1
    else:
        if (x,n) in d:
            return d[(x,n)]
        s = 0
        for i in range(max_in_group+1):
            s += count_digitsums(x-i, n-1, max_in_group)
        d[(x, n)] = s
        return s


def find_index_of_number(number_to_test):
    global max_in_group
    a = []
    while number_to_test != 0:
        a.append(number_to_test % (max_in_group + 1))
        number_to_test //= max_in_group + 1
    print("number to test:", ",".join(f'{i:03d}' for i in a[::-1]))
    print("numbers should sum to:", sum(a))

    x = sum(a)  # all the solutions need this sum
    leftx = 0  # the sum of the numbers to the left of the group being processed
    s = 0
    for k in range(len(a) - 1, -1, -1):
        for l in range(a[k]):
            # e.g. when 6 groups and a[5] = 304, first take 303, count number in 5 groups which sum to x-303
            s += count_digitsums(x - leftx - l, k, max_in_group)
        leftx += a[k]
    print("number of smaller solutions:", s)
    print("index of this solution:", s + 1)
    return s + 1


d = {}
find_index_of_number(number_to_test)

输出：

number to test: 304,153,525,784,175,759
numbers should sum to: 2700
number of smaller solutions: 180232548167366
index of this solution: 180232548167367