Given a number, find the next higher number which has the exact same set of digits as the original number

Question

You can do it in O(n) (where n is the number of digits) like this:

Starting from the right, you find the first pair-of-digits such that the left-digit is smaller than the right-digit. Let's refer to the left-digit by "digit-x". Find the smallest number larger than digit-x to the right of digit-x, and place it immediately left of digit-x. Finally, sort the remaining digits in ascending order - since they were already in descending order, all you need to do is reverse them (save for digit-x, which can be placed in the correct place in O(n)).

An example will make this more clear:

123456784987654321
start with a number

123456784 987654321
         ^the first place from the right where the left-digit is less than the right  
         Digit "x" is 4

123456784 987654321
              ^find the smallest digit larger than 4 to the right

123456785 4 98764321
        ^place it to the left of 4

123456785 4 12346789
123456785123446789
         ^sort the digits to the right of 5.  Since all of them except 
         the '4' were already in descending order, all we need to do is 
         reverse their order, and find the correct place for the '4'

---

Proof of correctness:

Let's use capital letters to define digit-strings and lower-case for digits. The syntax AB means "the concatenation of strings A and B". < is lexicographical ordering, which is the same as integer ordering when the digit-strings are of equal length.

Our original number N is of the form AxB, where x is a single digit and B is sorted descending.
The number found by our algorithm is AyC, where y ∈ B is the smallest digit > x (it must exist due to the way x was chosen, see above), and C is sorted ascending.

Assume there is some number (using the same digits) N' such that AxB < N' < AyC. N' must begin with A or else it could not fall between them, so we can write it in the form AzD. Now our inequality is AxB < AzD < AyC, which is equivalent to xB < zD < yC where all three digit-strings contain the same digits.

In order for that to be true, we must have x <= z <= y. Since y is the smallest digit > x, z cannot be between them, so either z = x or z = y. Say z = x. Then our inequality is xB < xD < yC, which means B < D where both B and D have the same digits. However, B is sorted descending, so there is no string with those digits larger than it. Thus we cannot have B < D. Following the same steps, we see that if z = y, we cannot have D < C.

Therefore N' cannot exist, which means our algorithm correctly finds the next largest number.

An almost-identical problem appeared as a Code Jam problem and has a solution here:

http://code.google.com/codejam/contest/dashboard?c=186264#s=a&a=1

Here's a summary of the method using an example:

34722641

A. Split the sequence of digits in two, so that the right part is as long as possible while remaining in decreasing order:

34722 641

(If the entire number is in decreasing order, there's no bigger number to be made without adding digits.)

At this point, you know there is no larger number that starts with the left part, because the right part is already as large as possible with the leftover digits.

B.1. Select the last digit of the first sequence:

3472(2) 641

B.2. Find the smallest digit in the second sequence that is larger than it:

3472(2) 6(4)1

What you're doing is finding the smallest possible increase to the left part.

B.3. Swap them:

3472(2) 6(4)1
->
3472(4) 6(2)1
->
34724 621

C. Sort the second sequence into increasing order:

34724 126

D. Done!

34724126

You split the number such that you knew there was no larger number with the same left part, you increased the left part by the smallest amount possible, and you made the remaining right part as small as possible, so you can be sure this new number is the smallest larger number that can be made with the same collection of digits.

Here's a compact (but partly brute force) solution in Python

def findnext(ii): return min(v for v in (int("".join(x)) for x in
    itertools.permutations(str(ii))) if v>ii)

In C++ you could make the permutations like this: https://stackoverflow.com/a/9243091/1149664 (It's the same algorithm as the one in itertools)

Here's an implementation of the top answer described by Weeble and BlueRaja, (other answers). I doubt there's anything better.

def findnext(ii):
    iis=list(map(int,str(ii)))
    for i in reversed(range(len(iis))):
        if i == 0: return ii
        if iis[i] > iis[i-1] :
            break        
    left,right=iis[:i],iis[i:]
    for k in reversed(range(len(right))):
        if right[k]>left[-1]:
           right[k],left[-1]=left[-1],right[k]
           break
    return int("".join(map(str,(left+sorted(right)))))

At minimum, here are a couple of example brute force String based solutions, that you should have been able to come up with right off the top of your head:

the list of digits in 38276 sorted is 23678

the list of digits in 38627 sorted is 23678

brute force increment, sort and compare

Along the brute force solutions would be convert to a String and brute force all the possible numbers using those digits.

Create ints out of them all, put them in a list and sort it, get the next entry after the target entry.

If you spent 30 minutes on this and didn't at least come up with at least a brute force approach, I wouldn't hire you either.

In the business world, a solution that is inelegant, slow and clunky but gets the job done is always more valuable than no solution at all, matter of fact that pretty much describes all business software, inelegant, slow and clunky.

function foo(num){
 sortOld = num.toString().split("").sort().join('');
 do{
    num++;
   sortNew = num.toString().split("").sort().join('');
 }while(sortNew!==sortOld);
 return num;
}

Your idea

I wanted to begin by finding the index of the first digit (from the right) that was less than the ones digit. Then I would rotate the last digits in the subset such that it was the next biggest number comprised of the same digits, but got stuck.

is pretty good, actually. You just have to consider not only the last digit but all digits of less significance than the currently considered. Since before that is reached, we have a monotonic sequence of digits, that is the rightmost digit smaller than its right neighbour. Regard

1234675
    ^

The next larger number having the same digits is

1234756

The found digit is exchanged for the last digit - the smallest of the considered digits - and the remaining digits are arranged in increasing order.