Data-Structures-and-Algorithms/Algorithms/BackTracking/SELECTION PROBLEMS/next_permuation.cpp at master · Manvityagi/Data-Structures-and-Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution
{
public:
    void nextPermutation(vector<int> &nums)
    {
        int n = nums.size();
        int sc;
        int fc = -1;
        for (int i = n - 2; i >= 0; i--)
        {
            //rightmost element after which a greater elt occurs
            if (nums[i + 1] > nums[i])
            {
                fc = i;
                break;
            }
        }

        if (fc == -1)
        {
            sort(nums.begin(), nums.end());
        }
        else
        {
            //rightmost element greater than fc
            for (sc = n - 1; sc > fc; sc--)
            {
                if (nums[sc] > nums[fc])
                {
                    break;
                }
            }
            swap(nums[fc], nums[sc]);
            sort(nums.begin() + fc + 1, nums.end());
            //  reverse(nums.begin() + fc + 1, nums.end());
        }
    }
};