The Next Permutation (with proof)

Problem:You have an array of numbers and you want to find the next lexicographic(the next in order) permutation.

Conventions and assumptions:

1. for the array with contents a,b,c,d…. when I say number I mean abcd…(array with contents 2,1,3,4 will be number 2134)
2. for a number left side means higher significant digits (lower array index) and right side means lower significant digits (higher array index)
3. we assume all array elements are distinct for simplicity , however the algorithm will also work for non distinct digits
4. the array indices are a1,a2,a3,….an
5. proofs are kind of informal

Okay, so how do we find the next permutation of a number?

So we have a number now and the next permutation will be a number bigger than the current number.

Step 1. We have to find two numbers ‘small’ and ‘big’ such that the small<big and ‘small’ occurs to the left of ‘big’ and we have to ensure that index of small is as large as possible. Also the number big should be as small as possible while still being greater than the number small (we will see why all this is necessary)
step 2. swap small and big
step 3. sort all the numbers appearing after the index of the big number (after swapping)

Claim 1 : ‘small’ should be to the left of ‘big’ always
Proof 1
This, I believe doesn’t require proof, it is easy to see and is intuitive. How else are you going to form a bigger number using the same digits?

Claim 2: the index of ‘small’ should be as large as possible
Proof 2
Consider number small1 whose index is n1 and the number big1 whose index is n2 (small1<big1 and n1<n2). Assume that index of small1 is not the largest and we are able to find small2 and big2 with index n3 and n4 respectively(small2<big2 and n3<n4) and n3>n1 (this is important).
Now we can form two numbers, one by swapping small1 and big1 call it num1 and the other by swapping small2 and big2 call it num2. num1 has a bigger number at index n1 and num2 has a bigger number at index n3 and since n3>n1 num2 has a change at its lesser significant digit positions.
So clearly num2<num1. (if you are not convinced ,write some numbers and try it out).
This means num1 will not be the next permutation since we were able to find num2 such that num2<num1.
Therefore it is crucial that index of the small number that we find is the largest possible.

Claim 3 : The ‘small’ number is always immediately to the left of a number bigger than it
i.e if we find the largest k such that array[k]<array[k+1] then array[k] will be our ‘small’ number.

Proof 3: (array[k] and small mean the same thing)

Lets assume that index of ‘small’ is k and array[k+1]<small. Lets say there exists array[k+x] (where x>1) such that array[k+x]>small.
So what we are saying above is the next number to ‘small’ ( to the right) is not bigger than ‘small’ and the bigger number is somewhere else ( obviously to the right of index k+1).

But now we see that (arr[k+x] is that bigger number we were talking about, the one that is not next to small)

a. array[k]>array[k+1]
b. array[k+x] > array[k] (where x>0 and x<=n)
from a and b
c. array[k+1]<array[k+x]

This means that the number at index k cannot be the ‘small’ number since we are able to find a number at k+1 , array[k+1] that satisfies all the properties of the ‘small’ number (note that ‘small’ numbers index should be as large as possible).
So if we find the largest k such that array[k]<array[k+1] then array[k] will be our ‘small’ number. This makes finding our small number really easy. ( O(n) )

Claim 4: When the small number is at the index k then the array will be of the form
…a[k+1]>a[k+2]>a[k+3]>……>a[n] (i.e it’ll be in descending order after index k)

Proof 4: (this will be helpful in finding the ‘big’ number also note that we still haven’t done anything to the array no swaps we have only found the ‘small’ number)

Assume this is not the case, say it is like this instead a[k+1]>a[k+2]<a[k+3] (or any other way that contradicts the claim) this contradicts our proof3 that k is the largest index such that a[k]<a[k+1] because we are able to find a[k+2]<a[k+3].
So our assumption is wrong and it is clear that ….a[k+1]>a[k+2]>a[k+3]>……>a[n] (i.e it’ll be in descending order after index k which is index of small number)

Okay now we have found the ‘small’ number how do we find the ‘big’ number?

The thing to be noted is that the ‘big’ number should be as small as possible while still being greater than the ‘small’ number and its index should be greater than k (we are going to swap this number with the ‘small’ number so if we don’t pick the smallest number then it will not result in the very next permutation after we swap them, try out a few examples to convince yourself,proving this is left out as an exercise to the reader , ahahaa I always wanted to say that.)
So we just start scanning from the last index and move towards the lower indices and when we find a[k+x]>a[k] (again x>0) then a[k+x] will be our ‘big’ number. Note that such a number always exists because a[k+1] is also such a number.

Swap the ‘big’ and ‘small’ numbers and we still see that what we showed in proof 4 holds.

why sort after index k+1?
Now that we have swapped them the numbers, the numbers after index k (k+1 to n ) should be sorted in ascending order because only that will give us the very next permutation (not hard to prove try it out yourself)
This sorting will be very easy because since they are already in descending order we just need to reverse the array after index k.

Aaand we are done 🙂

The algorithm:

step1. Find the largest k such that a[k]<a[k+1] (if no such number exists then there is no next permutation)

step 2. find the largest x such that a[k]<a[x] (and x>k)

step 3. swap a[k] and a[x]

step 4. reverse a[k+1] to a[n]

here’s the program:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

#define size 1000
bool Next_Permutation(char *a){
  bool possible=false;
  int small,big; // we will store index of small and big instead of the values
  int l=strlen(a);

  //finding small number
  for(int k=l-2;k>=0;k--){
    if(a[k]<a[k+1]){
      small=k;
      possible=true;
      break;
    }
  }
  if(possible){
    //finding big number
    for(int x=l-1;x>small;x--){
      if(a[x]>a[small]){
        big=x;
        break;
      }
    }
    //swap small and big
    swap(a[small],a[big]);

    //now reverse from index k+1(small) to n 
    for(int st=small+1,en=l-1;st<en;st++,en--){
      swap(a[st],a[en]);
    }
  }
  return possible;
}
int main(){
  char num[size];
  scanf("%s",num);//input number
  if(Next_Permutation(num))
    printf("%s\n",num);
  else
    printf("no next permutation\n");
  return 0;
}

or you could use this
http://www.cplusplus.com/reference/algorithm/next_permutation/