number of monotonely increasing numbers

Question

1. Introduction to problem

I am trying to find the number of monotonely increasing numbers with a certain number of digits. A monotonely increasing number with k digits can be written as

n = a_0 a_1 ... a_k-1

where a_i <= a_(i+1) for all i in range(0, k). A more concrete example are 123 or 12234489. I am trying to create a function such that

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

Because there are 45 numbers with two digits that are increasing, 11, 12, ..., 22, 23, ..., 88, 89, 99. And so forth.

I saw this as a nice opportunity to use recursion. I have tried to write a code that does this, however there is something wrong with the result. My psudo-code goes like this

2. Psudo-code

• Start with the numbers [1, 2, ..., 9] loop through these numbers. Increase length by one.
• Loop over the numbers [i, ..., 9] where last_digit was the number from the previous recursion.
• If length = number of digits wanted add one to total and return else repeat the steps above.

3. Code

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. Question:

Is my psudocode correct for finding these numbers? How can one use recursion correctly to tackle this problem?

I will not ask to find the error in my code, however some pointers or an example of code that works would be much obliged.

Answer 1

This can be computed in closed form.

We have a budget of 8 units, which we can allocate to each digit or to "leftovers". A digit with n units of budget allocated to it is n greater than the digit before it; for the first digit, if we allocate n units of budget there, its value is n+1. Leftover budget does nothing.

Budget allocations are in 1-to-1 correspondence with monotonely increasing numbers, as each budget allocation produces a monotonely increasing number, and each monotonely increasing number has a corresponding budget allocation. Thus, the number of monotonely increasing numbers of length k is the number of ways to allocate 8 units of budget to k+1 buckets, one bucket per digit and one bucket of leftovers.

By the classic stars and bars result, this is (8 + k) choose 8, or (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

For monotonely decreasing numbers, the same idea can be applied. This time we have 9 units of budget, because our digits can go from 9 down to 0 instead of starting at 1 and going up to 9. A digit with n units of budget allocated to it is n lower than the previous digit; for the first digit, n units of budget gives it value 9-n. The one caveat is that this counts 0000 as a four-digit number, and similarly for other values of k, so we have to explicitly uncount this, making the result ((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

Answer 2

You could use a simple recursion based on the following relation: the count of monotonic numbers of k digits starting at i (0<i≤9) is the sum of the counts of monotonic numbers of k-1 digits starting with j, i≤j≤9.

For k=1 the result is trivial: 10-i

It would lead to the following recursive function:

def num_increasing(ndigits, first=1):
    n = 0
    if ndigits == 1:
        n = 10 - first
    else:
        for digit in range(first, 10):
            n += num_increasing(ndigits - 1, digit)
    return n

For ndigits = 6, it gives 3003.

Answer 3

Here is a non-recursive solution to this:

def is_monotonic(num, reverse=False):
    num = str(num)
    # check if the string representation of num is same as the sorted one
    return num == ''.join(sorted(num, reverse=reverse))

def get_monotonic_nums(ndigit, reverse=False):
    start = 10**(ndigit-1) if reverse else int('1' * ndigit)
    end = 10**ndigit
    return sum(is_monotonic(num, reverse) for num in xrange(start, end))

And, then the usage:

>>> get_monotonic_nums(2)
45
>>> get_monotonic_nums(6)
3003

And, if you need the decreasing order:

>>> get_monotonic_nums(2, reverse=True)
54

Answer 4

This is what I came up with;

def is_monotonic(n):
    n = str(n)
    for x, y in zip(n[:-1], n[1:]):
        if x > y:
            return False
    return True

def get_monotonic_nums(digits):
    digits = abs(digits)
    start = 0 if digits == 1 else int('1{}'.format('0'*(digits-1)))
    end = start * 10 if start else 10
    for n in range(start, end):
        if is_monotonic(n):
            yield n

test;

len(list(get_monotonic_nums(2)))
45

Answer 5

After some searching on the internet I was able to figure out the following one liner solution. Based on the sum formula for the binomial coefficients. I now realize how slow my recursive solution was compared to this one.

def choose(n, k):
    """
    A fast way to calculate binomial coefficients by Andrew Dalke (contrib).
    """
    if 0 <= k <= n:
        ntok = 1
        ktok = 1
        for t in xrange(1, min(k, n - k) + 1):
            ntok *= n
            ktok *= t
            n -= 1
        return ntok // ktok
    else:
        return 0

def increasing(digit):
    return choose(digit + 9,9) - 1

def decreasing(digit):
    return choose(digit + 10,10) - 10*digit - 1