Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,31,3,2
3,2,11,2,3
1,1,51,5,1

Problem link

Solution

  • one naive approach is to first sort the array, recursively find all permutations on that array, the permutation right after the input one is what we want. In the worst case, it is O(n!)
  • Time Limit Exceeded, also this solution needs extra space
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        vector<int> v(num.begin(), num.end()); // make a new copy
        sort(v.begin(), v.end());
        vector<bool> u(num.size(), false);
        vector<int> next;
        bool equal = false;
        rec(num, v, u, next, equal);
        if (!equal) num = v;
    }
    
    void rec(vector<int> &num, vector<int> &v, vector<bool> &u, vector<int> &next, bool equal){
        for (int i=0; i<v.size(); i++){
            if (!u[i]){
                next.push_back(v[i]);
                if (next.size() == v.size()){
                    if (equal==false){
                        if (next == num) equal = true;
                    }else{
                        num = next;
                        return;
                    }
                }else{
                    u[i] = true;
                    rec(num, v, u, next, equal);
                    if (next.size() == v.size() && equal){
                        num = next;
                        return;   
                    } 
                    u[i] = false;
                }
                next.pop_back();
            }
        }
    }
};

In-place solution using swapping

  • expanding the right segment when all the elements in the right segment are sorted in decreasing order
  • after expansion, reverse all elements in the right segments
  • be careful about equal elements in the array
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        // find right segment
        int right;
        int n=num.size();
        int i;
        int j;
        for (i=n-1; i>=1 && num[i-1]>=num[i]; --i);
        if (i==0){// start from lowest possible order
            sort(num.begin(), num.end());
            return;
        }
        // i is boundary of the right segment, find next element in right that is greater than num[right-1]
        right = i;
        for (i=n-1; num[right-1]>=num[i]; --i);
        swap(num[right-1], num[i]);
        // reverse right:n-1
        i=right; j=n-1;
        while (i<j){
            swap(num[i],num[j]);
            i++;
            j--;
        }
    }
};
Advertisements
Next Permutation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s