Generating Permutations with Recursion: Fike’s Algorithm

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up] [Next]

Fike’s Algorithm

R. Sedgewick in [1] has attributed this algorithm to C. T. Fike [2]. Following is an implementation of this algorithm:

void fike(int s)
{
  int i;

  if(s == N-1)
  {
    print();
    return;
  }

  for(i = 0; i < N-s; i++)
  {
    /* Setup Block */
    if(i > 0)
      SWAP(s, s+i);

    fike(s+1);

    /* Cleanup Block */
    if(i > 0)
      SWAP(s, s+i);
  }
}

It is based on the idea that if each recursive call ﬁke(s + 1) keeps the subarray a[s + 1 : N − 1] intact upon return, we can pick each element of B correctly (without skipping or repeating any) one by one from indices s,s + 1,s + 2,…,N − 1.

Now, to ensure this, it enforces upon method ﬁke(s) the speciﬁcation that it must keep the input subarray a[s : N − 1] intact, for each s. For s = N − 1, this speciﬁcation is trivially met. For any other s, it is implemented by reversing the swap done before the recursive call ﬁke(s + 1), once that call returns. So, if ﬁke(s + 1) meets the speciﬁcation, each iteration of ﬁke(s) will also leave the subarray intact. This leads to the complete ﬁke(s) meeting the speciﬁcation. The correctness of this algorithm is thus established by Mathematical Induction.

An optimization is possible in above method. Note that all iterations (except the ﬁrst) do two swaps which involve the element initially at a[s]. We can exploit this fact and save some writes by assigning elements as below. The 6 writes of two swaps are now replaced by the 3 writes in an iteration:

  initial_a_s = a[s];

  for(i = 0; i < N-s; i++)
  {
    if(i > 0)
    {
      a[s] = a[s+i];
      a[s+i] = initial_a_s;
    }

    fike(s+1);

    if(i > 0)
      a[s+i] = a[s];
  }

  a[s] = initial_a_s;

[Prev] [Up] [Next]