查找第 n 次出现的千组，它们按词汇顺序总和为给定数字

Question

A 要求按词汇顺序（从低到高）到

的解决方案

a+b+c+d… = x

where a,b,c,d… is an arbitrary number of integers between 0-999 and x is a fixed integer

给出了一个答案，它使用 python.

完全有效地计算了这个

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

例如巨大的数字：

304,153,525,784,175,759

是 x=2700 的解，因为三组加起来等于 2700

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

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

有没有办法直接计算第n^th个解？ IE。对于一个已知解，计算有多少个解小于这个解。

Answer 1

编辑：此 post 仅解决如何在给定特定解决方案的情况下找到下一个解决方案。

OP追问：

给定索引 n 找到第 n^th 的解决方案，而不需要生成所有较早的解决方案。
给定一个解 a，找出存在多少个更小的解。

由于算法可以高效地找到下一个解决方案，您只需填写当前的解决方案即可。

这里有一种方法可以将当前解决方案填充为大整数或字符串：

start = 304153525784175759  # start = '304,153,525,784,175,759'
x = 2700
grouping = 3
max_in_group = 10**grouping - 1

if start is not None:
    if isinstance(start, str):
        a = [int(s) for s in start.split(',')[::-1]]
    else: # suppose start is a large integer
        a = []
        while start != 0:
            a.append(start % (max_in_group+1))
            start //= max_in_group+1
else: # no start value given, start with the smallest
    a = [x]

如果将此添加到的其余部分，您将获得输出：

304,153,525,784,175,759
304,153,525,784,176,758
304,153,525,784,177,757
304,153,525,784,178,756
304,153,525,784,179,755
304,153,525,784,180,754
304,153,525,784,181,753
304,153,525,784,182,752
304,153,525,784,183,751
304,153,525,784,184,750
304,153,525,784,185,749
304,153,525,784,186,748
...

Answer 2

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

对于给定的总和 x，找出某些固定数量 n 组的解有多少。这是一个递归函数。基本上，对于 n 组和求和 x，对于从 0 到 999 的所有 k，求和有多少解决方案 n-1 组和求和 x-k。由于经常使用相同的值调用递归函数，因此结果存储在记忆字典中，以便下次立即使用。
使用此函数计算存在多少个更小的解。这是一种类似的求和方式。例如。对于 6 组，从 304 开始，计算有多少 5 组从 303 开始，总和为 x-303，加上从 [=21] 开始的 5 组的数量=] 求和为 x-302，等等。然后，以 304,153 为起点，求 304,152 之后有多少 4 组求和为 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

查找第 n 次出现的千组，它们按词汇顺序总和为给定数字

Find nth occurence of groups of thousands which sum to a given number in lexical order

math

numbers

partition