如何使用给定的数字查找所有ndigit数字？

Question

我正在寻找一种算法，它能够找到所有的数，这些数都是n个数字，并且它们的数字之和等于x。由于代码是大型程序的一部分，因此需要较低的时间复杂度

示例：

findNumbers(2,5)

[14, 23, 32, 41, 50]

findNumbers(10,90)

[9999999999]

下面的代码似乎可以找到所需的数字，但效率有点低。例如findNumbers(5, 5)需要检查10000个数字，而只接受70个。对于更高的n，这种不匹配使其速度非常慢

什么是更快的方法

def firstNumber(n, x):
    # find the first number of n digits with x as sum of digits
    num9 = (x-1) // 9 # number of nines needed at the end of said first number
    f = 10**(n-1) # the first digit should be a 1 (or higher, if there are already n-1 nines)
    f += 10**num9 - 1 # num9 nines
    f += 10**num9 * (x - 1 - 9*num9) # add the rest just before the 9s
    return f

def sumOfDigits(x):
    s = 0
    while x > 0:
        s += x % 10
        x //= 10
    return s

def findNumbers(n, x, allow_all=False):
    f = firstNumber(n, x)
    nums = []
    while f < 10**n:
        if allow_all or sumOfDigits(f) == x:
            nums.append(f)
        f += 9 # if the sum of digits is x, all numbers must be equal modulo 9
    return nums

findNumbers(3, 5) # [104, 113, 122, 131, 140, 203, 212, 221, 230, 302, 311, 320, 401, 410, 500]

Answer 1

以下代码查找所有所需的数字。在中有一个参数max_in_group，您希望使用除基10以外的其他基运行

代码首先创建a个num_digits值的列表。列表中的每个条目代表一位数字。为了使代码更通用，可以设置最大数字。十进制是9，八角形是7。如果将3位小数加在一起，甚至是999。（现在打印的内容都是十进制的，但可以很容易地适应大于10的基数。）

这个数组a不一定需要所有数字都小于10。第一步将最后一个数字的溢出重新分配给前面的数字。当溢出需要一个额外的数字时，代码现在停止

在步骤2中，寻找继任者。如果没有溢出，倒数第二位只需加1。这将创建一个盈余（对于数字），该盈余应再次从最后一个数字中减去。当倒数第二位数字增长过大（已经是9）时，需要将其设置为0，并且应增加较早的数字，以此类推

在第三步中，最后一位数字需要用盈余进行调整。这可能会导致溢出，这将在步骤1中处理

要获得以零开始的数字，a可以用[0, ..., 0, desired_sum]初始化。要仅获取以1或更高开头的数字，应使用[1, 0, ..., 0, desired_sum-1]初始化a

请注意，由于Python没有do ... while或repeat ... until结构（如在类似C的语言中），因此这些循环需要使用while True和break编写

def find_nunbers(num_digits, desired_sum, max_iterations=100, max_in_digit=9):
    a = [0 for i in range(num_digits)]
    a[0] = desired_sum - 1
    a[num_digits - 1] = 1
    all_numbers_found = False
    while not all_numbers_found and max_iterations > 0:
        # step 1: while a[0] is too large: redistribute to the left
        i = 0
        while a[i] > max_in_digit:
            if i == num_digits - 1:
                all_numbers_found = True
                break
            a[i + 1] += a[i] - max_in_digit
            a[i] = max_in_digit
            i += 1
        if all_numbers_found:
            break

        num = sum(10 ** i * a[i] for i, n in enumerate(a))
        print(f"{num:}")  # print(a[::-1])

        # step 2:  add one to the penultimate group, while group already full: set to 0 and increment the
        #   group left of it;
        #   while the surplus is too large (because a[0] is too small) repeat the incrementing
        i0 = 1
        surplus = 0
        while True:  # needs to be executed at least once, and repeated if the surplus became too large
            i = i0
            while True:  # increment a[i] by 1, which can carry to the left
                if i == len(a):
                    all_numbers_found = True
                    break
                else:
                    if a[i] == max_in_digit:
                        a[i] = 0
                        surplus -= max_in_digit
                        i += 1
                    else:
                        a[i] += 1
                        surplus += 1
                        break
            if all_numbers_found:
                break
            if a[0] >= surplus:
                break
            else:
                surplus -= a[i0]
                a[i0] = 0
                i0 += 1

        # step 3: a[0] should absorb the surplus created in step 1, although a[0] can get out of bounds
        a[0] -= surplus
        surplus = 0
        max_iterations -= 1

find_nunbers(2, 5)
find_nunbers(10, 90)
find_nunbers(20, 90)

请注意，有278502200492534046020位数字和90位数字，因此无法将它们全部输出