python - 单调递增数

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增加1。

遍历数字[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.问题:

我的伪代码能正确找到这些数字吗？如何正确使用递归来解决此问题？

我不会要求在我的代码中找到错误，但是必须使用一些指针或有效的代码示例。

最佳答案

可以以封闭形式进行计算。

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

预算分配与单调递增的数字一对一对应，因为每个预算分配都会产生一个单调递增的数字，并且每个单调递增的数字都有一个对应的预算分配。因此，长度k的单调增加数的数量是将8个预算单位分配给k+1存储桶，每位数一个存储桶和一个剩余存储桶的方式的数目。

根据经典的stars and bars结果，这是(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

关于python - 单调递增数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37031296/