# Permutations in C++

By , 10 Sep 2009

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

//using iterators
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.

## Where Do We Go from Here?

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.

## History

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

 Wong Shao Voon Software Developer Singapore Member
Rather than to write an accolade of skills which I currently possess, these are the technologies, I am currently exploring:

• ASP.NET MVC 4
• C++14
• Garbage Collection
• GPU Computing
• H.264 video
• HTML5 and CSS3
• iOS
• SQL Server 2012

Votes of 3 or less require a comment

Hint: For improved responsiveness ensure Javascript is enabled and choose 'Normal' from the Layout dropdown and hit 'Update'.
 Search this forum Profile popups    Spacing RelaxedCompactTight   Noise Very HighHighMediumLowVery Low   Layout Open AllThread ViewNo JavascriptPreview   Per page 102550
 View All Threads First Prev Next
 permutation function 261349201 2 Mar '04 - 2:36
 Re: permutation function CBasicNet 2 Mar '04 - 13:59
 Re: permutation function matseke 3 Mar '04 - 18:53
 Re: permutation function Anonymous 14 Feb '05 - 20:24
 Last Visit: 31 Dec '99 - 18:00     Last Update: 21 May '13 - 19:36 Refresh 1