Table of Contents
Introduction
This article explains the technique of finding permutations, and provides source code for the recursive implementation. I will also explain how to use the STL template function next_permutation().
The formula for permutations is n!.
Explanation
Actually, finding permutations of a small group of numbers by yourself is not difficult, even without the help of computers. Let me show you the pattern.
Following are the permutations for two numbers {1,2}
12
21
Permutations of two numbers do not help us very much to understand the pattern.
The following is all six permutations for three numbers {1,2,3}
123
132
213
231
312
321
Let us only look at the permutations of which the first (leftmost) column is 1. Do you notice that the second column is in ascending order?
123
132
The next example is all 24 permutations for four numbers {1,2,3,4}
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
Let us look again at the permutations of which the first (leftmost) column is 1. Do you notice that the numbers in the second column are in ascending order?
1234
1243
1324
1342
1423
1432
Even for permutations where the leftmost column is 2, 3, or 4, the second column is always in ascending order. Whereby the second column is 1, 2, 3, or 4, the third column is also in ascending order.
Also notice the leftmost column is always in ascending order. You should be able to figure the inherent pattern by now. Let us go on to the source code section.
Source Code Section
The Recursive Way
I have written a recursive function, string_permutation(). Examples of using it can be found in string_perm_example.cpp.
The function declaration is as follows:
void string_permutation( std::string& orig, std::string& perm );
orig is the original permutation and perm is the permutated string. Given below is an example of how to use this string_permutation() function:
#include <string>
#include <iostream>
using namespace std;
void string_permutation( std::string& orig, std::string& perm )
{
if( orig.empty() )
{
std::cout<<perm<<std::endl;
return;
}
for(int i=0;i<orig.size();++i)
{
std::string orig2 = orig;
orig2.erase(i,1);
std::string perm2 = perm;
perm2 += orig.at(i);
string_permutation(orig2,perm2);
}
}
int main()
{
std::string orig="ABCDE";
std::string perm;
string_permutation(orig,perm);
cout<<"Complete!"<<endl;
system("pause");
return 0;
}
I also made a template function using std::vector called vector_permutation().
template <typename T, typename Func>
void vector_permutation(std::vector<T>& now,
std::vector<T> next, Func func);
Vector, now, is the current permutation. Vector, next, contains the next permutation. func is a function defined by you. If the permutation function finds permutations recursively, there must exist a way the user can process each permutation. The solution is a function pointer that takes in a parameter of type std::vector<T>. You are the one who defines this function. This way, encapsulation is achieved. You need not know how vector_permutation() internally works; you just need to know that whenever a new permutation is generated, it calls func() and passes func() the next vector and you just need to define func() to process the permutation.
vector_permutation() is defined in vector_perm.h. Shown below is an example of using vector_permutation():
#include <iostream>
#include <vector>
#include <string>
template <typename T, typename Func>
void vector_permutation(std::vector<T>& now,
std::vector<T> next, Func func)
{
int size=now.size();
if(size>0)
{
for(int cnt=0; cnt<size;++cnt)
{
std::vector<T> vt;
std::vector<T>::const_iterator it=now.begin();
for(int cnt1=0;cnt1<size;++cnt1)
{
if(cnt1==cnt)
{
++it;
continue;
}
else
vt.push_back(*it);
++it;
}
std::vector<T>::const_iterator it1=now.begin();
--it1;
for(int cnt2=0;cnt2<=cnt;++cnt2)
{
++it1;
}
next.push_back(*it1);
vector_permutation(vt,next,func);
next.pop_back();
}
}
else
{
func(next);
}
}
using namespace std;
void display(vector<char> perm)
{
for(vector<char>::iterator it= perm.begin();it!=perm.end();++it)
cout<<*it;
cout<<endl;
}
int main()
{
vector<char> ca;
ca.push_back('1');
ca.push_back('2');
ca.push_back('3');
ca.push_back('4');
vector<char> cnext;
vector_permutation(ca,cnext,display);
return 0;
}
The Non-Recursive Way
Fortunately for C++ programmers, the C++ Standard Template Library provides a next_permutation() template function and a corresponding prev_permutation() function defined in the <algorithm> header.
template<typename BidIt>
bool next_permutation(BidIt First,BidIt Last);
template<typename BidIt>
bool prev_permutation(BidIt First,BidIt Last);
The parameters are even simpler than the recursive one that I coded. First and Last are the first iterator and the one past the last iterator, respectively.
next_permutation() finds the next permutation while prev_permutation(), as its name implies, finds the previous permutation.
The Return Value
next_permutation() returns false when it encounters a sequence in descending order. It must be noted that, even when the return value is false, the next permutation is still generated. It is advisable to sort your array or container, in ascending order, before calling your first next_permutation(); that way, you know you get all your permutations when next_permutation() returns false, without calculating the total number of permutations, which translates into the total number minus 1 of next_permutation() iterative calls you must call.
prev_permutation() returns false when it encounters a sequence in ascending order. It must be noted that, even when the return value is false, the previous permutation is still generated. It is advisable to sort your array or container, in descending order, before calling your first prev_permutation(); that way, you know you get all your permutations when prev_permutation() returns false, without calculating the total number of permutations, which translates into the total number minus 1 of prev_permutation() iterative calls you must call.
Shown below are examples of using next_permutation() on an array of integers. I did not bother to write examples on how to use prev_permutation() because its usage is similar to that of next_permutation().
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int size=5;
void Display(int* iarr)
{
for(int i=0; i<size; ++i)
cout<<iarr[i]<<",";
cout<<endl;
}
int main()
{
int iarr[size] = {2,3,5,4,1};
sort(iarr,iarr+size);
Display(iarr);
while(next_permutation(iarr,iarr+size))
Display(iarr);
system("pause");
return 0;
}
Shown below are examples of using next_permutation() on a vector of integers:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Display(const vector<int>& vi)
{
for(size_t i=0; i<vi.size(); ++i)
cout<<vi[i]<<",";
cout<<endl;
}
int main()
{
vector<int> vi;
vi.push_back(3);
vi.push_back(5);
vi.push_back(4);
vi.push_back(1);
vi.push_back(2);
sort(vi.begin(),vi.end());
Display(vi);
while(next_permutation(vi.begin(),vi.end()))
Display(vi);
system("pause");
return 0;
}
next_permutation() also works for arrays and containers with repeated elements.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Display(const vector<int>& vi)
{
for(size_t i=0; i<vi.size(); ++i)
cout<<vi[i]<<",";
cout<<endl;
}
int main()
{
vector<int> vi;
vi.push_back(3);
vi.push_back(5);
vi.push_back(5);
vi.push_back(5);
sort(vi.begin(),vi.end());
Display(vi);
while(next_permutation(vi.begin(),vi.end()))
Display(vi);
system("pause");
return 0;
}
The output of the above program, with repeated elements, is as below:
3,5,5,5,
5,3,5,5,
5,5,3,5,
5,5,5,3,
Predicate Version
There also exists the predicate versions of next_permutation() and prev_permutation().
template<typename BidIt, class Pr>
bool next_permutation(BidIt First, BidIt Last, Pr Pred);
template<typename BidIt, class Pr>
bool prev_permutation(BidIt First, BidIt Last, Pr Pred);
On close examination of the source code of the non-predicate version and the predicate version, it seems the predicate version is to be used for classes (from which the objects are instantiated) that do not have the < operator defined. If you only need to use the permutation functions on POD (Plain Old Data), you just need to use the non-predicate versions. If you want to use them on your classes, please define the < operator for your class.
I will explain what the Pred parameter is before I conclude on this article.
Pred is a function pointer to a function that takes in two parameters of the type you are permutating. For example, if you are operating on ints, the int type is passed. This function compares the two parameters and returns true if the first parameter is lesser than the second parameter; else, false. You have to define this function.
Pred can also be a function object. But, the explanation of a function object is beyond the scope of this article. You can find that out in your C++ book.
We can find permutations of an r sequence picked from an n sequence, if we have next_combination(). Bingo! There you have it! I have written a next_permutation()'s equivalent, called next_combination(), for finding combinations. Please read it in my combination article!
Update: I have also written Permutations in C++, Part 2 which you can continue to read on, if you are interested to know how to find permutations on multi-core processors.
- 7 Sep. 2009 - Updated the article with code examples and more information.
- 26 Nov. 2006 - Replaced
char_permutation with string_permutation.
- 7 Sep. 2003 - Updated source.
- 1 Sep. 2003 - First release on CodeProject.
