Home

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


[Prev]   [Up]   

Fischer-Krause Algorithm

Now we will use the relationship among elements of P and P′ to generate P′ from P. Properties (1) and (2) can be used to locate the first element am−1 in P at which P and P′ differ. ak can be searched in the subsequent elements of P, with its desired property. Below is an outline of how we can generate P′ from P:

  1. By reading elements in P backwards starting at aN−1, find m such that:
    am > am+1 > am+2 > ... > aN− 1

    and am−1 < am.

    Note, it is possible that m = N − 1. Also, when we have m = 0, we must have the largest permutation already in a, and we can terminate.

  2. Again, by reading elements in P backwards starting at aN−1, find first (hence smallest in set S) element ak such that: ak > am−1.
  3. Swap am−1 and ak.
  4. We must be having all elements after the m− 1 index in decreasing order. Make them in increasing order simply by reversing this portion of the array (last N −m elements). We have now arrived at the next permutation P′ in array a.

Now the algorithm to generate all permutations of array a is straightforward. Generate the smallest permutation by sorting a in increasing order. Starting with this permutation, keep generating the next permutation by above method. Terminate upon reaching the largest permutation as detected in step (1) above.

Below C program shows the next() function which generates the next permutation of the current permutation in array a. If a already contains the largest permutation, it returns 0, otherwise 1. Function to sort array a initially is not shown; the sample array is already sorted.

#include <stdio.h>  
 
int a[] = {1,2,3,4,5,6,7,8,9};  
int N = 9;  
 
void print(void);  
int next(void);  
 
int main(void)  
{  
  /* sort a[] in increasing order */  
 
  print();  
 
  while(next())  
    print();  
 
  return 0;  
}  
 
#define SWAP(i, j) {int t; t = a[i]; a[i] = a[j]; a[j] = t;}  
 
int next(void)  
{  
  int m, k;  
 
  /* Find m */  
  m = N-1;  
 
  while(m > 0 && a[m-1] > a[m])  
    m--;  
 
  /* (m == 0 OR a[m-1] < a[m]) is TRUE */  
 
  if(m == 0)  
  {  
    /* Permutation in a[] is the largest one */  
    return 0;  
  }  
 
  /* (a[m-1] < a[m]) is TRUE */  
 
  /* Find k. Since a[m] is larger than a[m-1], we are sure  
   * to find required a[k] within the index range [m, N-1].  
   * Hence, no lower bound checking for variable k is needed  
   * in the below loop.  
   */  
 
  k = N-1;  
 
  while(a[k] < a[m-1])  
    k--;  
 
  /* (a[k] > a[m-1]) is TRUE */  
 
  SWAP(m-1, k);  
 
  /* Reverse the order of elements from a[m] to a[N-1] */  
  int s = m;  
  int e = N-1;  
 
  while(s < e)  
  {  
    SWAP(s, e);  
    s++;  
    e--;  
  }  
 
  return 1;  
}  
 
void print(void)  
{  
  int i;  
 
  for(i = 0; i < N; i++)  
    printf("%d ", a[i]);  
 
  printf("\n");  
}

References

[1]   R. Sedgewick. Permutation Generation Methods. ACM Comput. Surv., Vol 9 (2) (1977), 137–164.

[Prev]   [Up]   

Copyright © 2021 Nitin Verma. All rights reserved.