N3buchadnezzar N3buchadnezzar - 6 months ago 31
Python Question

number of monotonely increasing numbers

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

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
Comments