1, 4, 11 lines C++


  • 47

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

  • 0
    Q

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

  • 0

    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.


  • 0
    S

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


  • 0

    @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.


  • 0
    S
    This post is deleted!

  • 0
    S

    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...).


  • 0
    R

    you are excellent !! learned a lot..


  • 0
    M

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

Log in to reply
 

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