1  
   2  #include <stdio.h>
   3  
   4  void printv(int v[], int n) {
   5  	int i;
   6  
   7  	for (i = 0; i < n; i++)
   8  		printf("%d ", v[i]);
   9  	printf("\n");
  10  }
  11  
  12  /*!
  13  	This just swaps the values of a and b
  14  
  15  	i.e if a = 1 and b = 2, after
  16  
  17  		SWAP(a, b);
  18  
  19  	a = 2 and b = 1
  20  */
  21  #define SWAP(a, b) a = a + b - (b = a)
  22  
  23  /*!
  24  	Generates the next permutation of the vector v of length n.
  25  
  26  	@return 1, if there are no more permutations to be generated
  27  
  28  	@return 0, otherwise
  29  */
  30  int next(int v[], int n) {
  31  	/* P2 */
  32  	/* Find the largest i */
  33  	int i = n - 2;
  34  	while ((i >= 0) && (v[i] > v[i + 1]))
  35  		--i;
  36  
  37  	/* If i is smaller than 0, then there are no more permutations. */
  38  	if (i < 0)
  39  		return 1;
  40  
  41  	/* Find the largest element after vi but not larger than vi */
  42  	int k = n - 1;
  43  	while (v[i] > v[k])
  44  		--k;
  45  	SWAP(v[i], v[k]);
  46  
  47  	/* Swap the last n - i elements. */
  48  	int j;
  49  	k = 0;
  50  	for (j = i + 1; j < (n + i) / 2 + 1; ++j, ++k)
  51  		SWAP(v[j], v[n - k - 1]);
  52  
  53  	return 0;
  54  }
  55  
  56  int main(int argc, char *argv[]) {
  57  	int v[128];
  58  	int n = 3;
  59  
  60  	/* The initial permutation is 1 2 3 ...*/
  61  	/* P1 */
  62  	int i;
  63  	for (i = 0; i < n; ++i)
  64  		v[i] = i + 1;
  65  	printv(v, n);
  66  
  67  	int done = 1;
  68  	do {
  69  		if (!(done = next(v, n)))
  70  			printv(v, n); /* P3 */
  71  	} while (!done);
  72  
  73  	return 0;
  74  }