Saturday, April 7, 2012

Iterative, recursive and heap algorithms to generate permutations

A very good article on iterative and recursive algorithms for generating permutations of an array is here:
http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

I shall shamelessly lift the algorithms listed in the page, for my reference here in the blog.
(Just for reference, another good algorithm is described at http://introcs.cs.princeton.edu/java/23recursion/Permutations.java.html)
Recursive algorithm for Permutations
It's executed with a call visit(0). Global variable level is initialized to -1 whereas every entry of the array Value is initialized to 0.
  void visit(int k)
  {
    level = level+1; Value[k] = level;    // = is assignment
    if (level == N)  // == is comparison
      AddItem();     // to the list box
    else
      for (int i = 0; i < N; i++)
        if (Value[i] == 0)
          visit(i);
    
    level = level-1; Value[k] = 0;
  }

  void AddItem()
  {
  // Form a string from Value[0], Value[1], ... Value[N-1].
  // At this point, this array contains one complete permutation.
  // The string is added to the list box for display.
  // The function, as such, is inessential to the algorithms.
  }

Lexigraphic order to find the next permutation
Permutation f precedes a permutation g in the lexicographic (alphabetic) order iff for the minimum value of k such that f(k)≠ g(k), we have f(k) < g(k). Starting with the identical permutation f(i) = i for all i, the second algorithm generates sequentially permutaions in the lexicographic order. The algorithm is described in [Dijkstra, p. 71].
  
  void getNext()
  {
    int i = N - 1;
    while (Value[i-1] >= Value[i]) 
      i = i-1;

    int j = N;
    while (Value[j-1] <= Value[i-1]) 
      j = j-1;
  
    swap(i-1, j-1);    // swap values at positions (i-1) and (j-1)

    i++; j = N;
    while (i < j)
    {
      swap(i-1, j-1);
      i++;
      j--;
    }
  }
B. Heap's algorithm 
Heap's short and elegant algorithm is implemented as a recursive method HeapPermute [Levitin, p. 179]. It is invoked with HeapPermute(N).
  
void HeapPermute(int n)
{
  if (n == 1) 
    AddItem();
  else {
    for (int i = 0; i < n; i++) 
      HeapPermute(n-1);
      if (n % 2 == 1)  // if n is odd
        swap(0, n-1);
      else            // if n is even
        swap(i, n-1);
}

No comments:

Post a Comment