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

**Conventions and assumptions:**

- 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)
- for a number left side means higher significant digits (lower array index) and right side means lower significant digits (higher array index)
- we assume all array elements are distinct for simplicity , however the algorithm will also work for non distinct digits
- the array indices are a1,a2,a3,….an
- 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/