Permutations in C++

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 finding the total number of permutations is factorial of number of elements.

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.

The permutations for two numbers {1,2}


12
21

Permutations of two numbers do not help you very much to understand the pattern.

All six permutations for three numbers {1,2,3}


123
132
213
231
312
321

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

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

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. When 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. By now, you should be able to figure the inherent pattern. Go on to the source code section.

Source Code Section

The recursive way

I had 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.

Below is an example on 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 callback function that you define. If the permutation function finds permutations recursively, a way must exist that the user can process each permutation. The solution is a function pointer that takes in a parameter of the type std::vector<T>. You define this function. In this way, encapsulation is achieved. You need not know how vector_permutation() internally works; you just know that, whenever a new permutation is generated, it calls func and passes func the ‘next’ vector; you just need to define func() to process the permutation.

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 whereas 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(); in that way, you know you get all your permutations when next_permutation() returns false, without calculating the total number of permutations, which translates into 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(); in that way, you know you get all your permutations when prev_permutation() returns false, without calculating the total number of permutations, which translates into total number minus 1 of prev_permutation() iterative calls you must call.

Below are examples of using next_permutation() on array of integers. I didn’t 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;
}

Below are examples of using next_permutation() 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,

Prediate versions

The prediate versions of next_permutation() and prev_permutation() also exist.


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

The prediate version is to be used for classes (from which the objects are instantiated) that do not have the < operator defined. If you only use the permutation functions on POD (Plain Old Data), you just need to use the non-prediate 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 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 define this function.

Pred also can 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 You Go from Here?

You can find permutations of r sequence picked from n sequence if you 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.

Revision History

  • 02 Sept 2009: Updated the article with code examples and more information
  • 26 Nov 2006: Replaced char_permutation with string_permutation

More by Author

Get the Free Newsletter!

Subscribe to Developer Insider for top news, trends & analysis

Must Read