C++ Coding Reference: next_permutation() and prev_permutation()

C++ algorithm header provides you access to next_permutation() and prev_permutation() which can be used to obtain the next or previous lexicographically order. With an array or vector or string (or other STL containers) of size N, there are total N! (factorial) permutations. The (next or previous) permutation algorithms are mostly in-place which mean that it will modify the given list or vector.

The C++ permutation algorithm functions are quite handy, which can be used to solve algorithm puzzles, like the following:

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:

1 2 3 4 5 6 7 8

[   [1,2,3],   [1,3,2],   [2,1,3],   [2,3,1],   [3,1,2],   [3,2,1] ]

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

std::next_permutation()

The std::next_permutation() takes 3 parameters, the first two are mandatory/required while the third one is the optional. The first parameter is the start of the container (which could be vector/array or string), and the second parameter marks the end of the STL container. For example:

1
2

vector<int> nums({1, 2, 3, 4, 5});
next_permutation(begin(nums), end(nums)); // nums is now {1, 2, 3, 5, 4}

vector<int> nums({1, 2, 3, 4, 5});
next_permutation(begin(nums), end(nums)); // nums is now {1, 2, 3, 5, 4}

The third parameter is used to provide a custom lexicographical comparator. The above example is essentially the same as the following:

1
2
3
4

vector<int> nums({1, 2, 3, 4, 5});
next_permutation(begin(nums), end(nums), [](auto &a, auto &b) {
   return a < b;
}); // nums is now {1, 2, 3, 5, 4}

vector<int> nums({1, 2, 3, 4, 5});
next_permutation(begin(nums), end(nums), [](auto &a, auto &b) {
   return a < b;
}); // nums is now {1, 2, 3, 5, 4}

The std::next_permutation() will permutate the vector container and return if there is still a next permutation. For example:

1
2
3
4
5
6

vector<int> nums({1, 2, 3, 4, 5});
// nums is now {1, 2, 3, 5, 4} and the function returns true
next_permutation(begin(nums), end(nums)); 
vector<int> nums2({5, 4, 3, 2, 1});
// nums2 is now {1, 2, 3, 4, 5} and the function returns false
next_permutation(begin(nums2), end(nums2)); 

vector<int> nums({1, 2, 3, 4, 5});
// nums is now {1, 2, 3, 5, 4} and the function returns true
next_permutation(begin(nums), end(nums)); 
vector<int> nums2({5, 4, 3, 2, 1});
// nums2 is now {1, 2, 3, 4, 5} and the function returns false
next_permutation(begin(nums2), end(nums2)); 

It is worth to note that, when the original list is considered the last lexicographical order, the next_permutation() will still permutate the list which virtually rewinds to first lexicographical sequence.

Now, we can easily solve the algorithm puzzle mentioned at the beginning – don’t forget to push the current order into the final list.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    vector<vector<in>> permute(vector<int>& nums) {
        vector<vector<int>> r;
        sort(begin(nums), end(nums));
        r.push_back(nums);
        while (next_permutation(begin(nums), end(nums))) {
            r.push_back(nums);
        }
        return r;
    }
};

class Solution {
public:
    vector<vector<in>> permute(vector<int>& nums) {
        vector<vector<int>> r;
        sort(begin(nums), end(nums));
        r.push_back(nums);
        while (next_permutation(begin(nums), end(nums))) {
            r.push_back(nums);
        }
        return r;
    }
};

We need to sort the original vector so that all permutations can be returned. The algorithm complexity is dominated by sorting which is O(NlogN). The next_permutation() runs at O(N) complexity.

std::prev_permutation()

Syntactically, the std::prev_permutation() is the same as next_permutation() however it returns the last lexicographical sequence/order. We can easily deduce that, the next_permutation() is the same as prev_permutation() when passing the third parameter as the reversed version. For example, the following two are equivalently the same.

1
2
3
4
5
6

next_permutation(begin(nums), end(nums), [](auto &a, auto &b) {
   return a < b;
});
prev_permutation(begin(nums), end(nums), [](auto &a, auto &b) {
   return a > b;
});

next_permutation(begin(nums), end(nums), [](auto &a, auto &b) {
   return a < b;
});
prev_permutation(begin(nums), end(nums), [](auto &a, auto &b) {
   return a > b;
});

We can also use next_permutation() or prev_permutation() on strings. For example:

1
2
3

string s = "12345";
next_permutation(begin(s), end(s));  // s becomes 12354
prev_permutation(begin(s), end(s));  // s becomes 12345

string s = "12345";
next_permutation(begin(s), end(s));  // s becomes 12354
prev_permutation(begin(s), end(s));  // s becomes 12345

We can also use prev_permutation() to solve the puzzle:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    vector<vector<in>> permute(vector<int>& nums) {
        vector<vector<int>> r;
        sort(rbegin(nums), rend(nums));  // sorting in the reverse order
        r.push_back(nums);
        while (prev_permutation(begin(nums), end(nums))) {
            r.push_back(nums);
        }
        return r;
    }
};

class Solution {
public:
    vector<vector<in>> permute(vector<int>& nums) {
        vector<vector<int>> r;
        sort(rbegin(nums), rend(nums));  // sorting in the reverse order
        r.push_back(nums);
        while (prev_permutation(begin(nums), end(nums))) {
            r.push_back(nums);
        }
        return r;
    }
};

One difference is to sort the original array in the reverse order – by passing the reverse iterators e.g. rbegin() and rend(). Alternatively, we can use std::reverse() after the usual sort() in ascending order.

–EOF (The Ultimate Computing & Technology Blog) —