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


About the Author

Wong Shao Voon

I guess I'll write here what I does in my free time, than to write an accolade of skills which I currently possess. I believe the things I does in my free time, say more about me.

When I am not working, I like to watch Japanese anime. I am also writing some movie script, hoping to see my own movie on the big screen one day.

I like to jog because it makes me feel good, having done something meaningful in the morning before the day starts.

I also writes articles for CodeGuru; I have a few ideas to write about but never get around writing because of hectic schedule.

Downloads

Comments

  • Recursive Link List for strings

    Posted by Andre Long on 11/05/2012 04:46pm

    How would you implement your recursive logic for the permutation of a link list of strings?

    Reply
  • this will be better

    Posted by cppgohan on 10/21/2008 09:37am

    std::vector::const_iterator it1=now.begin(); for(int cnt2=0;cnt2 Reply

  • Article not updated.

    Posted by CBasicNet on 12/03/2006 08:43pm

    Hi guys, do not read this article because it is not the updated one, it is still the old one. I'll notify Codeguru webmaster of this problem.

    • Articles is updated.

      Posted by CBasicNet on 12/04/2006 08:38pm

      Brad has resolved it for me. Thanks, Brad!

      Reply
    Reply
  • Your update too frequent!!!

    Posted by Legacy on 09/04/2003 12:00am

    Originally posted by: Programmer

    make the meal done before asking guest

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • With JRebel, developers get to see their code changes immediately, fine-tune their code with incremental changes, debug, explore and deploy their code with ease (both locally and remotely), and ultimately spend more time coding instead of waiting for the dreaded application redeploy to finish. Every time a developer tests a code change it takes minutes to build and deploy the application. JRebel keeps the app server running at all times, so testing is instantaneous and interactive.

  • You probably have several goals for your patient portal of choice. Is "community" one of them? With a bevy of vendors offering portal solutions, it can be challenging for a hospital to know where to start. Fortunately, YourCareCommunity helps ease the decision-making process. Read this white paper to learn more. "3 Ways Clinicians can Leverage a Patient Portal to Craft a Healthcare Community" is a published document owned by www.medhost.com

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds