/*
	n-Factorial Counting Algorithm

	This program is to test a n-Factorial 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

	n-Factorial 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 n-index.
	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 n-index, 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 n-index
	is because the previous positions will have already
	swapped values of index and less and and all values
	of n-index+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 n-index:
		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 n-index:
		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 zero-based index exceeds the floor of n/2-1.  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 2|3 4
		   |

		    |
		1 2 3 4 5
		    |

*/

#include <stdlib.h>
#include <stdio.h>
#include <strings.h>

#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, "n-Factorial Counting Algorithm\n");
		fprintf(stderr, "Copyright(c)2002 by Donna Whisnant\n\n");
		fprintf(stderr, "Usage: fcount <n>\n\n");
		fprintf(stderr, "Where <n> = 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<n; i++) {
		Seq[i] = i+1;
		factor *= i+1;
	}

	count = 0;
	done = 0;
	index = 0;
	flag = 0;
	while (!done) {
		if (flag == 0) {
			for (i=0; i<n; i++) printf("%2d ", Seq[i]);
			printf("\n");
			count++;

			if (count > 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<n) && (done)); i++) if (Seq[i]>=Seq[i-1]) 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] > n-index) Seq[index] = index+1;

		for (i=0; i<n; i++) {
			if (i == index) continue;
			if (Seq[i] == Seq[index]) {
				Seq[i] = val;
				if ((val == n-index) && (i == n-1-index)) {
					flag=1;
				} else {
					flag=0;
				}
				break;
			}
		}

		if (flag) {
			index++;
		} else {
			index=0;
		}
	}

	printf("\n\nCount=%ld\n\n", count);

	if (count == factor) {
		printf("Success!\n\n");
	} else {
		printf("Expected %ld values, calculated only %ld\n\n", factor, count);
	}

	free(Seq);

	return 0;
}