#include <stdio.h>

typedef enum { ok = 0, wrong_argc, oom, overflow } ret_t;

static void get_permutation( int n, unsigned long long *fact, int *p, int i );
static void generate_recursively( int n, int *p, char **argv );

int main( int argc, char **argv )
{
  ret_t result;
  int n;

  result = ok;
  n = argc - 1;
  if( n > 0 )
	{
	  int *p;

	  p = ( int * ) malloc( n * sizeof( int ) );
	  if( p != NULL )
		{
		  unsigned long long i;
		  unsigned long long *fact;
		  unsigned long long nfact;

		  fact = ( unsigned long long * ) 
			malloc( n * sizeof( unsigned long long ) );
		  if( fact != NULL )
			{
			  fact[ 0 ] = 1;
			  for( i = 1 ; i < n ; ++i )
				{
				  fact[ i ] = fact[ i - 1 ] * i;
				  if( ( fact[ i ] < fact[ i - 1 ] ) ||
					  ( fact[ i ] / i != fact[ i - 1 ] ) )
					{
					  free( fact );
					  generate_recursively( n, p, argv );
					  return ok;
					}
				}
			  nfact = fact[ n - 1 ] * n;
			  for( i = 0 ; i < nfact ; ++i )
				{
				  int j;

				  get_permutation( n, fact, p, i );
				  for( j = 0 ; j < n ; ++j )
					{
					  printf( "%s", argv[ p[ j ] + 1 ] );
					}
				  puts( "" );
				}
			  free( fact );
			}
		  else
			{
			  fprintf( stderr, "permutations: cannot allocate %i bytes\n", 
					   n * sizeof( unsigned long long * ) );
			  result = oom;
			}
		  free( p );
		}
	  else
		{
		  fprintf( stderr, "permutations: cannot allocate %i bytes\n", 
				   n * sizeof( int ) );
		  result = oom;
		}
	}
  else
	{
	  fprintf( stderr, 
			   "usage: permutations a1 a2...\n"
			   "\n\tPrints all possible permutations of arguments"
			   "\n\tCompiled from " __FILE__ " at " __DATE__ "\n\n" );
	  result = wrong_argc;
	}
  return result;
}

static void get_permutation( int n, unsigned long long *fact, int *p, int i )
{
  int j;

  for( j = 0 ; j < n ; ++j )
	{
	  p[ j ] = -1;
	}
  for( j = 0 ; j < n ; ++j )
	{
	  int pos;
	  int k;
	  int l;

	  pos = ( i / fact[ n - 1 - j ] ) % ( n - j );
	  for( k = 0, l = 0 ; ; k = ( ++k ) % n )
		{
		  if( p[ k ] == -1 )
			{
			  if( l == pos )
				{
				  break;
				}
			  ++l;
			}
		}
	  p[ k ] = j;
	  /* printf( "i: %lli j: %i pos: %i k: %i\n", i ,j ,pos ,k ); */
	}
}

static void generate_recursively_from( int n, int *p, int index, char **argv )
{
  if( index < n )
	{
	  int pos;

	  for( pos = 0 ; pos < n - index ; ++pos )
		{
		  int skipped;
		  int i;

		  for( i = skipped = 0 ; i < n ; ++i )
			{
			  if( p[ i ] == -1 )
				{
				  if( skipped >= pos )
					{
					  break;
					}
				  ++skipped;
				}
			}
		  p[ i ] = index;
		  generate_recursively_from( n, p, index + 1, argv );
		  p[ i ] = -1;
		}
	}
  else
	{
	  int j;

	  for( j = 0 ; j < n ; ++j )
		{
		  printf( "%s", argv[ p[ j ] + 1 ] );
		}
	  puts( "" );
	}
}

static void generate_recursively( int n, int *p, char **argv )
{
  int j;

  for( j = 0 ; j < n ; ++j )
	{
	  p[ j ] = -1;
	}
  generate_recursively_from( n, p, 0, argv );
}