# 9 Lines of C++ code with Comments

• ``````class Solution {
public:
void nextPermutation(vector<int> &num)
{
if (num.empty()) return;

// in reverse order, find the first number which is in increasing trend (we call it violated number here)
int i;
for (i = num.size()-2; i >= 0; --i)
{
if (num[i] < num[i+1]) break;
}

// reverse all the numbers after violated number
reverse(begin(num)+i+1, end(num));
// if violated number not found, because we have reversed the whole array, then we are done!
if (i == -1) return;
// else binary search find the first number larger than the violated number
auto itr = upper_bound(begin(num)+i+1, end(num), num[i]);
// swap them, done!
swap(num[i], *itr);
}
};
``````

You might need to think for a while why this would work.

• very clear. work like a charm

• class Solution {
public:

``````void nextPermutation(vector<int>& nums) {
if(!nums.size() || nums.size() == 1)
return;

int i = nums.size() - 1;
for(; i - 1 >= 0 && nums[i - 1] >= nums[i]; --i);
if(i == 0)
{
for(int front = 0, back = nums.size() - 1; front < back; swap(nums[front++], nums[back--]));
}
else if(i - 1 >= 0)
{
int pivot = --i;
for(;i + 1 < nums.size() && nums[pivot] < nums[i + 1]; ++i);
swap(nums[pivot], nums[i]);
for(int front = pivot + 1, back = nums.size() - 1; front < back; swap(nums[front++], nums[back--]));
}
}
``````

};