## 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 `int`

s, 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.