Heap’s algorithm: permutation of ‘ n’ different objects.

Heap’s algorithm generates all possible permutations of n objects. It was first proposed by B. R. Heap in 1963. It works by the principle of fixing one element and then swapping others elements in all combinations.

Working Example

we assume an array of integers namely : a,b,c. Now we are to apply the heaps algo to its use.

so basically we have to get something like this:

so we are basically using a sort of backtracking process.We may notice that swapping and freezing is all what we are doing.The following classification can be put into a very compact code.

The code

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

void printarr(int arr[],int n)
{ int i;
for( i=0;i<n;i++)
{
cout<<arr[i]<<” “;

}
cout<<endl;

}
void permute(int arr[],int size,int n)
{ int i;
if(size==1)
{
printarr(arr,n);
return;
}

for(i=0;i<n;i++)
{
permute(arr,size-1,n);

if(size%2==1)
swap(arr[0],arr[size-1]);
if(size%2==0)
swap(arr[i],arr[size-1]);

}

}

int main()
{
int arr[]={1,2,3};

int n = sizeof(arr)/sizeof(arr[0]);
permute(arr,n,n);
}

Now if anyone is wondering about the surprising swap function in their, i have to say that it’s a STL library function.Hence it’s not a big deal to find all possible permutation’s of an array or sometimes a string.Heap’s algorithm can always come to help.