//-------------------------------------------------------------------
//	perms.cpp
//
//	This program generates all permutations on {1,2,...,N}.
//	It is adapted from pseudocode appearing in Shimon Even, 
//	"Algorithmic Combinatorics," Macmillan (1973).  In this
//	algorithm the permutations form a 'cycle' in which each 
//	member is obtained from its predecessor by swapping two
//	adjacent elements (i.e., by a 'transposition').       
//
//		to compile:  $ g++ perms.cpp -o perms
//		to execute:  $ ./perms 
//
//	programmer: ALLAN CRUSE
//	written on: 10 JUL 2011
//-------------------------------------------------------------------

#include <stdio.h>	// for printf() 

#define	N 4

int	X[ N+1 ], S[ N+1 ], A[ N+1 ], k, y, i, j, t, m, c;

int main( int argc, char **argv )
{
	// array initializations
	for( k = 0; k <=N; k++) { X[k] = 0; S[k] = 1; A[k] = k; }

	k = N; y = 0; m = 1; c = 0;
	while ( k > 0 )
		{
		if ( m > 0 ) 
			{
			++c;
			printf( "\n#%d:\t", c );
			for (i = 1; i <= N; i++) printf( "%d ", A[i] );
			m = 0;
			}

		X[k] += S[k];
		if (( X[k] != 0 )&&( X[k] != k ))
			{
			j = X[k] + y;
			i = j+1;
			t = A[j];
			A[j] = A[i];
			A[i] = t;
			k = N;
			y = 0;
			m = 1;
			}
		else	{
			if ( X[k] == 0 ) ++y;
			S[k] = -S[k];
			--k;
			}
		}
	printf( "\n\n" );	
}