For example the permutation sequence {0, 1, 2, 3, 4} can be followed by {1, 0, 2, 3, 4} where both differ only in their values at the first and second positions.

- Ordered list of permutations
- Pattern in the ordered list
- Tree pre-order traversal
- Implementation of algorithm

Below is an example of numbered permutations in order for the case of n=4.

index(I) sequence(p) 0 - 0 1 2 3 1 - 1 0 2 3 2 - 0 2 1 3 3 - 2 0 1 3 4 - 1 2 0 3 5 - 2 1 0 3 6 - 0 1 3 2 7 - 1 0 3 2 8 - 0 3 1 2 9 - 3 0 1 2 10 - 1 3 0 2 11 - 3 1 0 2 12 - 0 2 3 1 13 - 2 0 3 1 14 - 0 3 2 1 15 - 3 0 2 1 16 - 2 3 0 1 17 - 3 2 0 1 18 - 1 2 3 0 19 - 2 1 3 0 20 - 1 3 2 0 21 - 3 1 2 0 22 - 2 3 1 0 23 - 3 2 1 0

There are two types of newI that are created, if they exist, from any given I and so there are two functions, say

Starting from the base permutation p={0, 1, 2, 3}, where I=0, the output is essentially:

cause I newI p of newI A 0 1 - 1 0 2 3 A 1 3 - 2 0 1 3 A 3 9 - 3 0 1 2 B 9 15 - 3 0 2 1 B 15 21 - 3 1 2 0 B 3 5 - 2 1 0 3 A 5 11 - 3 1 0 2 B 11 17 - 3 2 0 1 B 17 23 - 3 2 1 0 A 1 7 - 1 0 3 2 B 7 13 - 2 0 3 1 B 13 19 - 2 1 3 0 A 0 2 - 0 2 1 3 A 2 8 - 0 3 1 2 B 8 14 - 0 3 2 1 B 14 20 - 1 3 2 0 B 2 4 - 1 2 0 3 A 4 10 - 1 3 0 2 B 10 16 - 2 3 0 1 B 16 22 - 2 3 1 0 A 0 6 - 0 1 3 2 B 6 12 - 0 2 3 1 B 12 18 - 1 2 3 0

To get the corresponding sequence p from a given value of I, go to generating permutations.

- starts with a value I,
- followed by the total number of newI generated from it, say T,
- followed by T pairs of values of the form (newI A) or (newI B) - without the brackets.

(newI A) means the value newI is generated from the value I by the function A. Same thing for (newI B).

```
#include <stdio.h>
void function_A (int n, int I, int level);
void function_B (int n, int I, int level);
int factorial (int k);
void add (int process, int n, int I, int newI, int chr);
int tree[100000][20];
// the tree describes the running of the algorithm.
// a pre-order traversal of the tree corresponds
// to the permutations as printed on the screen.
int main()
{
int n;
printf("Enter n : "); // get value of n
scanf("%d", &n);
printf("\n");
add(0,0,0,0,0); // initialise the tree
function_A (n, 0, 1); // run the algorithm
add(2,n,0,0,0); // print the tree
return 0;
}
void function_A (int n, int I, int level)
{
int i, newI;
for(i=level; i<n; i++)
{
newI = I + factorial(i);
add(1, n, I, newI, 'A');
function_B (n, newI, i);
}
}
void function_B (int n, int I, int level)
{
function_A (n, I, level+1);
int newI = I + factorial(level);
if(newI >= factorial(level+1)) return; // base case
add(1, n, I, newI, 'B');
function_B (n, newI, level);
}
int factorial (int k)
{
int i, ans=1;
for(i=k; i>0; i--) ans*=i;
return ans;
}
/*
The 'add' function below:
- initialises the tree, when process==0
- adds newI as a child to the node I, when process==1
- prints the tree as an adjacency-list, when process==2
*/
void add (int process, int n, int I, int newI, int chr)
{
int i, j;
if(process==0)
{
for(i=0; i<10000; i++)
tree[i][0]=0;
}
else if(process==1)
{
tree[I][0]++;
tree[I][tree[I][0]*2] = newI;
tree[I][tree[I][0]*2+1] = chr;
}
else if(process==2)
{
printf("Tree:\n");
for(i=0; i<factorial(n); i++)
{
printf(" %d %d ", i, tree[i][0]);
for(j=1; j<=tree[i][0]; j++)
printf(" %d %c", tree[i][j*2], (char)tree[i][j*2+1]);
printf("\n");
}
}
else printf("process unknown\n");
}
```