python - 单调递增数的数量

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 .等等。

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

2。伪代码

• 以数字 [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。问题:

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

我不会要求找出我的代码中的错误，但是非常有必要提供一些指针或有效的代码示例。

Answer 1

这可以用封闭形式计算。

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

预算分配与单调递增的数字是一一对应的，因为每个预算分配产生一个单调递增的数字，每个单调递增的数字都有对应的预算分配。因此，长度为k的单调递增数的个数就是将8个单位的预算分配给k+1个桶的方法数，每个数字一个桶，一个桶剩饭剩菜。

由经典stars and bars结果，这是 (8 + k) 选择 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) 选择 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