-5

On re-arranging digits in number 1862 next highest number is 2168

On re-arranging digits in number 22405 next highest number is 22450

What is an algorithm for finding next highest number?

overexchange
  • 15,768
  • 30
  • 152
  • 347
  • Just what do you mean by "next highest number"? Do you mean the next highest of all the numbers that can be gotten by rearranging the decimal digits of the original number? And by "mathematical process" do you mean an algorithm or code in some computer language or something else? I do have such code, in Object Pascal (Delphi), and would love to translate that to Python, but you need to clarify what you want. You also need to tell us the work you have done on this problem so far and show any code you have made. This is not a homework-answering service. – Rory Daulton Nov 29 '16 at 17:19
  • 1
    Possible duplicate of [Algorithm to find next greater permutation of a given string](http://stackoverflow.com/questions/1622532/algorithm-to-find-next-greater-permutation-of-a-given-string) – phuclv Nov 30 '16 at 16:27
  • that's what [`std::next_permutation`](http://stackoverflow.com/a/16680391/995714) is for – phuclv Nov 30 '16 at 16:28

1 Answers1

2

Here is a summary of an algorithm that does what you want. If you want more details, code, or a proof of the correctness of the algorithm, show us more of what you have done so far.

Let's use 1862 as an example. Scan the digits of that number from the right-most digit to the left until you find a consecutive pair of digits where the left digit is smaller than the right digit. In this case that is the 18. Let's call that left digit the "pivot" position (1 here). You will now rearrange the digits in the number starting with that pivot. Replace the pivot with the next-larger digit that is anywhere to the right of it (2 in this case). Then after that digit, place all the other digits that used to be at or right of the pivot (186 in this case) in ascending order (168 here). The result is your answer 2168.

In your other example 22405 you scan back and stop at 05. You replace the 0 with the 5 then put the other digit(s), 0 in this case, after it in increasing order. So you leave the 224 alone and end up with 22450.

If, in your backwards scan, you do not find any consecutive pair of digits where the left digit is smaller than the right digit, then there is no larger number with those digits.

There is a trick to speed up the placement of the digits in increasing order, but I'll leave that to you.

Rory Daulton
  • 21,934
  • 6
  • 42
  • 50