/*
nFactorial Counting Algorithm
This program is to test a nFactorial Counting Algorithm.
That is, one that can count efficiently through all unique
combinations of numbers. For example:
1,2,3
2,1,3
3,1,2
1,3,2
2,3,1
3,2,1
nFactorial Counting Algorithm Copyright(c)2002 Donna Whisnant
Written June 23, 2002
This algorithm starts with a linear sequence of numbers
from 1 to n. Such as 1,2,3,4.
The first (index=0) position is incremented from index+1 to nindex.
On each increment, the position that used to hold the
current position's value is changed to the current position's
old value and all other positions are left unmodified.
For example:
1,2,3,4 > 2,2,3,4 > 2,1,3,4
This continues until the position exceeds nindex, at which
point the position wraps back to index+1:
1,2,3,4
2,1,3,4
3,1,2,4
4,1,2,3
1,4,2,3
2,4,1,3
3,4,1,2
4,3,1,2
1,3,4,2
2,3,4,1
3,2,4,1
4,2,3,1
Whenever a wrap back to index+1 occurs, if the swap is
with the opposing position in the sequence, then index
is bumped and incrementation occurs on the next position:
4,2,3,1
1,2,3,4 (4,2,3,1 becomes 1,2,3,4, but during
the wrap, the opposing position
was swapped with the current index
position. Therefore, we wrap the
current position to index+1 and
increment index)
1,3,2,4
2,3,1,4
3,2,1,4
4,2,1,3
1,2,4,3
2,1,4,3
3,1,4,2
4,1,3,2
1,4,3,2
2,4,3,1
3,4,2,1
4,3,2,1
The sequence is complete when it has been reversed.
The reason a position is counted from index+1 to nindex
is because the previous positions will have already
swapped values of index and less and and all values
of nindex+1 and higher with this position.
The opposing positions is best seen on higher 'n' values:
4,7,5,3,6,2,1
5,7,4,3,6,2,1
6,7,4,3,5,2,1
7,6,4,3,5,2,1 > 1,6,4,3,5,2,7 (first and last swapped)
So, bump to next, remember each position counts to nindex:
1,6,4,3,5,2,7 > 1,2,4,3,5,6,7 (second and next to last swapped)
So, bump to next, remember each position counts to nindex:
1,2,4,3,5,6,7 > 1,2,5,3,4,6,7
Therefore, 1,2,5,3,4,6,7 comes immediately after 7,6,4,3,5,2,1
A quicker method of detecting the sequence end is to see
when zerobased index exceeds the floor of n/21. In the
n=7 example above, when index>2 we are finished.
For n=4, when index>1 we are finished.
This is because the sequence is symmetric around the
center:

1 23 4


1 2 3 4 5

*/
#include
#include
#include
#define DEF_FAC_SIZE 4
int main(int argc, char *argv[])
{
int n;
int i;
int *Seq;
int done;
int val;
int count;
int index;
int flag;
long factor;
if (argc != 2) {
n = DEF_FAC_SIZE;
fprintf(stderr, "nFactorial Counting Algorithm\n");
fprintf(stderr, "Copyright(c)2002 by Donna Whisnant\n\n");
fprintf(stderr, "Usage: fcount \n\n");
fprintf(stderr, "Where = factorial size\n\n");
printf("Using default factorial of %ld\n\n", n);
} else {
n = atoi(argv[1]);
if (n <= 0) {
fprintf(stderr, "ERROR : Specified Factorial must be >=1\n\n");
return 3;
}
printf("Factorial of %ld\n\n", n);
}
Seq = malloc(sizeof(int) * n);
if (Seq == NULL) {
fprintf(stderr, "ERROR : Out of memory\n\n");
return 1;
}
factor = 1;
for (i=0; i factor) {
fprintf(stderr, "ERROR : Exceeded limit\n\n");
free(Seq);
return 2;
}
/* We are done once the sequence is reversed: */
/* done = 1;
for (i=1; ((i=Seq[i1]) done=0;
if (done) continue;
*/
}
/* A faster way to see when we are done: */
if (index > ((n/2)1)) {
done=1;
continue;
}
val=Seq[index];
Seq[index]++;
if (Seq[index] > nindex) Seq[index] = index+1;
for (i=0; i