单数增加的数量

Question

1.问题简介

我试图找到具有一定数字位数的单调增加数字的数量.带有k数字的单调递增数可以写为

n = a_0 a_1 ... a_k-1

在哪里a_i <= a_(i+1)为所有人i in range(0, k).一个更具体的例子是123或12234489.我正在尝试创建一个这样的功能

increasing(2) = 45
increasing(3) = 165
increasing(4) = 495
increasing(5) = 1287
increasing(6) = 3003

因为有45个数字,两个数字正在增加,11, 12, ..., 22, 23, ..., 88, 89, 99.等等.

我认为这是一个使用递归的好机会.我试图编写一个执行此操作的代码,但结果有问题.我的psudo代码是这样的

2. Psudo代码

• 从数字[1, 2, ..., 9]循环开始这些数字.增加length一个.
• 循环数字[i, ..., 9],其中last_digit是前一次递归的数字.
• 如果length = number of digits wanted添加一个total和return别人重复上述步骤.

3.代码

global total
total = 0
nums = range(1, 10)

def num_increasing(digits, last_digit = 1, length = 0):
    global total

    # If the length of the number is equal to the number of digits return
    if digits == length:
        total += 1
        return

    possible_digits = nums[last_digit-1::]

    for i in possible_digits:
        last_digit = i
        num_increasing(digits, last_digit, length + 1)
    return total

if __name__ == '__main__':

    num_increasing(6)
    print total

4.问题:

我的psudocode找到这些数字是否正确？如何正确使用递归来解决这个问题？

我不会要求在我的代码中找到错误,但是一些指针或代码的示例将非常有用.

Answer 1

这可以以封闭形式计算。

我们有 8 个单位的预算，我们可以将其分配给每个数字或“剩余”。n分配给它的预算单位的数字n大于其前面的数字；对于第一位数字，如果我们n在那里分配预算单位，则其值为n+1。剩余的预算没有任何作用。

预算分配与单调递增数一一对应，每个预算分配产生一个单调递增数，每个单调递增数都有相应的预算分配。因此，单调递增的长度数就是将8个预算单位分配给桶、每个数字一个桶和一个剩余桶的k方式的数量。k+1

根据经典的星形和条形结果，这是(8 + k) choose 8, 或(8+k)!/(8!k!)：

def monotone_number_count(k):
    total = 1
    for i in xrange(k+1, k+9):
        total *= i
    for i in xrange(1, 9):
        total //= i
    return total

对于单调递减的数字，可以应用相同的想法。这次我们有 9 个预算单位，因为我们的数字可以从 9 向下到 0，而不是从 1 开始一直到 9。n分配了预算单位的数字n比前一个数字低；对于第一位数字，n预算单位赋予其价值9-n。需要注意的是，这被视为0000一个四位数字，对于 的其他值也类似k，因此我们必须显式地对其进行计数，从而得到结果((9 + k) choose 9) - 1：

def monotonely_decreasing_number_count(k):
    total = 1
    for i in xrange(k+1, k+10):
        total *= i
    for i in xrange(1, 10):
        total //= i
    total -= 1
    return total