# A mathematical solution accepted as best in C, well explained

• The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

• Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
• Find the largest index l greater than k such that a[k] < a[l].
• Swap the value of a[k] with that of a[l].
• Reverse the sequence from a[k + 1] up to and including the final element a[n].

As for the demonstration, it will be presented in the comments of the solution as follows for your better understanding.

``````void swap(int* p, int* q)
{
int t = *p; *p = *q; *q = t;
}
void reverse(int* nums, int begin, int end)
{
for(int i = begin; i < (begin+end+1)/2; i++)
swap(nums+i, nums+end+begin-i);
}
void nextPermutation(int* nums, int size)
{
int i=size-1, j=size-1;
while(i>0 && nums[i]<=nums[i-1]) i--; //make sure the [i..size-1] is descending order;
if(i==0) //the whole array is descending now, reverse it to the smallest as problem says;
{
reverse(nums, 0, size-1);
return ;
}
while(nums[j] <= nums[i-1]) j--; //find the first bigger one backwards;
swap(nums+j, nums+i-1); //ensure the next is bigger;
reverse(nums, i, size-1); //since [i..size-1] is descending, after reverse it will be ascending and as a result - [i..size-1] will be the smallest - the smallest in the bigger results - the next permutation;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.