Generate permutations of a string in C++

This code uses Heap’s Algorithm(https://en.wikipedia.org/wiki/Heap%27s_algorithm) to generate all distinct. This algorithm can be written in any language but we provide implementation in C++ below.

Following C++11 features are used:

  • std::swap to swap string indices
  • std::string to represent the string

It is recommended that the following code be compiled on a new compiler (like GCC 4.9+) and use the GCC O3 compiler optimization so as to achieve best performance even for larger string lengths.

//Generate all permutations of a string using Heap's Algorithm 
//(https://en.wikipedia.org/wiki/Heap%27s_algorithm)


#include "bits/stdc++.h"

using namespace std;


void permute(int n,string str){
	int c[n],i;

	for(i=0;i<n;i++)
		c[i]=0;

	cout<<str<<endl;
	i=0;

	while(i<n){
		if (c[i]<i){
			if(i%2==0)
				swap(str[0],str[i]);
			else
				swap(str],str[i]);
			cout<<str<<endl;
			c[i]+=1;
			i=0;
		}
		else{
			c[i]=0;
			i+=1;	
		}
	}
	
}



int main(int argc, char const *argv[])
{
	string R;
	cout<<"Enter string:";
	cin>>R;

	cout<<"\n\n****************PERMUTATIONS FOR "<<R<<" *******************\n\n";
	permute(R.length(),R);
	return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *