## Generating all permutations of a string with Heap's method

### by Adrian Lita - on 2018-06-19

Generating permutations can sometimes be a difficult task. The number of permutations is given by the factorial of the total number of elements:

``````unsigned int total_permutations(unsigned int n)
{
unsigned int p = 1;
for (int i = 2; i <= n; i++)
{
p *= i;
}
return p;
}
``````

The function above only works to a n of about 12 on 32bit machines before the result exceeds that. So for n equals 12 we have about 479.001.600!!! permutations possible. For sure, that takes a lot of time to process.

Anyhow, for a given string s, Heap's algorithm proved to be fastest in computing all possible permutations:

``````/*
Function to calculate the number of permutations (factorial of n)
*/
unsigned int total_permutations(unsigned int n)
{
unsigned int p = 1;
for (int i = 2; i <= n; i++)
{
p *= i;
}
return p;
}

/*
Heap's algorithm for generating all permutations
*/
void heap_permutations(const int n, char *s)
{
if (n == 1)
{
cout << s << endl;
}
else
{
for (int i = 0; i < n; i++)
{
heap_permutations(n - 1, s);
if (n % 2 == 1)
{
swap(s, s[n - 1]);
}
else
{
swap(s[i], s[n - 1]);
}
}
}
}

int main()
{