# 1, 4, 11 lines C++

• Solution 1

Just for info: There's a library function that does the job, even going from totally reverse sorted to sorted:

``````void nextPermutation(vector<int>& nums) {
next_permutation(begin(nums), end(nums));
}
``````

Solution 2

Using library functions for all building blocks of the algorithm. Very nice how they all play together, notice the total lack of `+1`/`-1`, it all fits exactly.

``````void nextPermutation(vector<int>& nums) {
auto i = is_sorted_until(nums.rbegin(), nums.rend());
if (i != nums.rend())
swap(*i, *upper_bound(nums.rbegin(), i, *i));
reverse(nums.rbegin(), i);
}
``````

Solution 3

Doing it all on my own (except `swap`, let's not be silly):

``````void nextPermutation(vector<int>& nums) {
int i = nums.size() - 1, k = i;
while (i > 0 && nums[i-1] >= nums[i])
i--;
for (int j=i; j<k; j++, k--)
swap(nums[j], nums[k]);
if (i > 0) {
k = i--;
while (nums[k] <= nums[i])
k++;
swap(nums[i], nums[k]);
}
}
``````

Solution 4

Ok, let's be silly after all and not even use `swap` :-)

``````void nextPermutation(vector<int>& nums) {
int i = nums.size() - 1, k = i, tmp;
while (i > 0 && nums[i-1] >= nums[i])
i--;
for (int j=i; j<k; j++, k--)
tmp = nums[j], nums[j] = nums[k], nums[k] = tmp;
if (i > 0) {
k = i--;
while (nums[k] <= nums[i])
k++;
tmp = nums[i], nums[i] = nums[k], nums[k] = tmp;
}
}``````

• thanks for you post, I learned a lot from them. besides, a minor flaw, you 3rd and 4th version doesn't handle the case if nums.empty()==true.

below is my code handle the empy case.

``````class Solution {
public:
void nextPermutation(vector<int>& nums) {
int *q, *p, *pend=&nums[nums.size()], *rp=&nums[nums.size()-1], *rpend=&nums[-1];
auto prev=(long long)INT_MIN-1;
for(;rp!=rpend && *rp>=prev;prev=*rp--) {}
if(rp!=rpend) {
for(p=pend-1;p!=rp && *p<=*rp;--p) {}
if(p!=rp) std::swap(*p,*rp);
}
for(p=rp+1, q=pend-1;p!=pend && q-p>0;++p,--q) { std::swap(*p,*q); }
}
};``````

• Yeah, I just supported what the OJ wanted. But I agree it makes sense to also support the empty vector. I fixed that now (just had to change some `i` to `i > 0`), thanks.

• This can be improved a bit more with a binary search on the right side for the number to be swapped (`k` value).

• @severb I don't think that's better. In practice, you don't have a single isolated `nextPermutation` call with one of the rare very "bad" cases but iterate through many cases, and the average search range is very small - less than two elements. The overhead for binary search is detrimental then. And in theory, by which I mean complexity class, even if you only consider worst cases, the complexity class stays the same, as I'm only searching through a range that I just completely went through twice anyway.

• This post is deleted!

• Agreed it's the same complexity class and probably not better in practice; it's just a lower constant (and thus a bit faster) in the worst case scenario (231111...).

• you are excellent !! learned a lot..

• Very nice library use! A minor suggestion is that iter_swap can be used instead of swap:

``````iter_swap(i, upper_bound(nums.rbegin(), i, *i));
``````

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