A mathematical solution accepted as best in C, well explained


  • 1

    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;
    }

Log in to reply
 

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