# The Steinhaus-Johnson-Trotter Algorithm

``````
/*===================================================================*/
/* C program for distribution from the Combinatorial Object Server.  */
/* Generate permutations by transposing adjacent elements            */
/* via the Steinhaus-Johnson-Trotter algorithm. This is              */
/* the same version used in the book "Combinatorial Generation."     */
/* Both the permutation (in one-line notation) and the positions     */
/* being transposed (as a 2-cycle) are output.                       */
/* The program can be modified, translated to other languages, etc., */
/* so long as proper acknowledgement is given (author and source).   */
/* Programmer: Frank Ruskey, 1995.                                   */
/* The latest version of this program may be found at the site       */
/* http://sue.uvic.ca/~cos/inf/perm/PermInfo.html                    */
/*===================================================================*/

#include <stdio.h>
#include <conio.h>

int NN, i, count=0;
int p, pi;      /* The permutation and its inverse */
int dir;             /* The directions of each element  */

void PrintPerm()
{
int i;
/* uncomment if you want to print the index of each perm  */
/*
count = count + 1;
printf( "[%8d] ", count );
*/
for (i=1; i <= NN; ++i)
printf( "%d", p[i] );
} /* PrintPerm */;

void PrintTrans( int x, int y )
{
printf( " (%d %d)", x, y );
printf( "\n" );
} /* PrintTrans */;

void Move( int x, int d )
{
int z;
PrintTrans( pi[x], pi[x]+d );
z = p[pi[x]+d];
p[pi[x]] = z;
p[pi[x]+d] = x;
pi[z] = pi[x];
pi[x] = pi[x]+d;
} /* Move */;

void Perm ( int n )
{
int i;
if (n > NN)
PrintPerm();
else
{
Perm( n+1 );
for (i=1; i<=n-1; ++i)
{
Move( n, dir[n] );
Perm( n+1 );
}
dir[n] = -dir[n];
} // else
} /* of Perm */;

void main ()
{
printf( "Enter n: " );
scanf( "%d", &NN );
printf( "\n" );
for (i=1; i<=NN; ++i)
{
dir[i] = -1; p[i] = i;
pi[i] = i;
}
Perm ( 1 );
printf( "\n" );
getch();
} // main()
``````

The above algorithm was found at:  http://www.theory.csc.uvic.ca/~cos/inf/perm/PermInfo.html
Email all questions and concerns to cos@theory.csc.uvic.ca

[]

[] | [] | [] | [] | []
[] | []
[] | [] | []
[]