Next highest int from digits

Next highest int from digits is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Given a zero or positive integer, the task is to generate the next largest integer using only the given digits.

• Numbers will not be padded to the left with zeroes.
• If there is no next higest integer return zero.

Algorithm 1

1. Generate all the permutations of the digits and sort into numeric order.
2. Find the number in the list.
3. Return the next highest number from the list.

The above could prove slow and memory hungry for numbers with large numbers of digits, but should be easy to reason about its correctness.

Algorithm 2

1. Scan right-to-left through the digits of the number until you find a digit with a larger digit somewhere to the right of it.
2. Exchange that digit with the digit on the right that is both more than it, and closest to it.
3. Order the digits to the right of this position, after the swap; lowest-to-highest, left-to-right. (I.e. so they form the lowest numerical representation)

E.g:

    n = 12453
<scan>
    12_4_53
<swap>
    12_5_43
<order-right>
    12_5_34

    return: 12534

This second algorithm is faster and more memory efficient, but implementations may be harder to test. One method of testing ,(as used in developing the task), is to compare results from both algorithms for random numbers generated from a range that the first algorithm can handle.

Task requirements

Calculate the next highest int from the digits of the following numbers:

• 0
• 9
• 12
• 21
• 12453
• 738440
• 45072010
• 95322020

Optional stretch goal

• 9589776899767587796600

Python

Python: Algorithm 2

<lang python>def closest_more_than(n, lst):

   "(index of) closest int from lst, to n that is also > n"
   #print('closest_more_than2' + str((n, lst)))
   large = max(lst) + 1
   return lst.index(min(lst, key=lambda x: (large if x <= n else x)))

def nexthigh(n):

   "Return nxt highest number from n's digits using scan & re-order"
   assert n == int(abs(n)), "n >= 0"
   this = list(int(digit) for digit in str(int(n)))[::-1]
   mx = this[0]
   for i, digit in enumerate(this[1:], 1):
       if digit < mx:
           mx_index = closest_more_than(digit, this[:i + 1])
           this[mx_index], this[i] = this[i], this[mx_index]
           this[:i] = sorted(this[:i], reverse=True)
           return int(.join(str(d) for d in this[::-1]))
       elif digit > mx:
           mx, mx_index = digit, i
   return 0

if __name__ == '__main__':

   for x in [0, 9, 12, 21, 12453, 738440, 45072010, 95322020,
             9589776899767587796600]:
       print(f"{x:>12_d} -> {nexthigh(x):>12_d}")</lang>

Output:

Note underscores are used in integer representations to aid in comparisons.

           0 ->            0
           9 ->            0
          12 ->           21
          21 ->            0
      12_453 ->       12_534
     738_440 ->      740_348
  45_072_010 ->   45_072_100
  95_322_020 ->   95_322_200
9_589_776_899_767_587_796_600 -> 9_589_776_899_767_587_900_667

Python: Algorithm 1

(I would not try it on the stretch goal, otherwise results as above. <lang python>from itertools import permutations

def nexthigh(n):

   "Return next highest number from n's digits using search of all digit perms"
   assert n == int(abs(n)), "n >= 0"
   this = tuple(str(int(n)))
   perms = sorted(permutations(this))
   for perm in perms[perms.index(this):]:
       if perm != this:
           return int(.join(perm))
   return 0</lang>