查找第n个出现的成千上万的组，它们按词法顺序求和成给定的数字 [英] Find nth occurence of groups of thousands which sum to a given number in lexical order

问题描述

一个上一个问题要求以词法顺序(从最低到最高)到

A previous question asked for the solutions in lexical order (lowest to highest) to

a + b + c + d ... = x

a+b+c+d… = x

其中a，b，c，d ...是介于0-999和x之间的任意整数 是一个固定的整数

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

给出了一个答案，可以使用python对其进行全面有效地计算.

An answer was given which fully computes this efficiently using python.

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

However, for very large numbers, the loop could take years to complete.

例如，巨大的数字:

304,153,525,784,175,759

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

is a solution for x=2700 since the groups of threes add up to 2700

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

但是，要遍历算法以获得等于该数字的第n ^th 个解决方案，则需要花费数月或数年.

However, to loop through the algorithm to get the n^th solution which equals this number would take months or years.

有没有一种方法可以直接计算第n ^th 个解决方案? IE.对于已知的解决方案，要计算出比该解决方案少的解决方案.

Is there a way to calculate the n^th solution directly? I.e. for a known solution, to calculate how many solutions are less than this one.

推荐答案

这里是一种查找解决方案索引的方法(或:有多少个较小的解决方案).该代码分为两部分:

Here is a way to find the index of a solution (or: how many smaller solutions there are). The code has two parts:

• 对于给定的总和x，对于固定数目的n个组，找到多少个解决方案.这是一个递归函数.基本上，对于n个组并求和x，对于从0到999的所有k，求和使用n-1个组求和并求和x-k的总数.由于经常使用相同的值来调用递归函数，因此结果存储在备忘录字典中，以备下次使用.

• Find how many solutions there are for some fixed number n of groups for a given sum x. This is a recursive function. Basically, for n groups and sum x, for all k from 0 to 999, sum up how many solutions there are with n-1 groups and sum x-k. As the recursive function often is called with the same values, the results are stored in a memoization dictionary to be used immediately the next time.

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

Use this function to calculate how many smaller solutions there exist. This is a similar way of summing. E.g. for 6 groups and starting with 304, calculate how many 5-groups there are which start after 303 and sum to x-303, add the number of 5-groups which start with 302 and sum to x-302, etc. Then, taking 304,153 as start, find how many 4-groups start after 304,152 and sum to x-304-152, etc.

这是完整的代码，已针对相当多的输入进行了测试(由上一个程序生成的测试).给定的18位数字只需几秒钟.

Here is the complete code, tested for quite some inputs (test generated by the previous program). It just takes a few seconds for the given 18-digit number.

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个出现的成千上万的组，它们按词法顺序求和成给定的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！