number of monotonely increasing numbers

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 by Serge Ballesta for number of monotonely increasing numbers

You could use a simple recursion based on the following relation: the count of monotonic numbers of k digits starting at i (0

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 by AKS for number of monotonely increasing numbers

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 by user2357112 for number of monotonely increasing numbers

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 by Nizam Mohamed for number of monotonely increasing numbers

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 by N3buchadnezzar for number of monotonely increasing numbers

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  

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72