Adrian Lita

Generating all permutations of a string with Heap's method

by Adrian Lita - on 2018-06-19

Keywords: #permutation #string #strings #academic #snippet #heap
Permalink: https://adrian.lita.me/blog_string-permutation-heap-method.html
 

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[0], s[n - 1]);
      }
      else
      {
        swap(s[i], s[n - 1]);
      }
    }
  }
}

int main()
{
  char a[] = "adrian";
  cout << "Total permutations of \"" << a << "\": " << total_permutations(strlen(a)) << endl;
  heap_permutations(strlen(a), a);

  return 0;
}

The example generates all permutations of the string "adrian" and displays it on screen. The heap_permutations function is a recursive function.