#include <stdio.h>
#include <string.h>

#define DIM (1<<VDIM)



/*
#define VDIM 3
char *vnames = "123";
int sig[] = { 1, 1, 1 };
char *xnames[DIM] = { "1", "E1", "E2", "E3", "E12", "E31", "E23", "E123" };
*/

/*
#define VDIM 3
char *vnames = "012";
int sig[] = { 0, 1, 1 };
char *xnames[DIM] = { "1", "E0", "E1", "E2", "E01", "E20", "E12", "E012" };
*/

#define VDIM 4
char *vnames = "0123";
int sig[] = { 0, 1, 1, 1 };
char *xnames[DIM] = { "1", "E0", "E1", "E2", "E3", "E01", "E02", "E03", "E12", "E31", "E23",
	"E021", "E013", "E032", "E123", "E0123" };



char *names[DIM];
int signs[DIM];
int nelts[VDIM+1];
int grade[DIM];

int fac(int n) { return n < 2 ? 1 : n*fac(n-1); }
int ncr(int n, int k) { return fac(n)/(fac(k)*fac(n-k)); }

char**
genrecur(char **np, char *buf, char *p, int k, int n)
{
	int i, j;

	if(n == 0) {
		*p = '\0';
		*np++ = strdup(buf);
		return np;
	}

	for(i = k; i < VDIM; i++) {
		*p = vnames[i];
		np = genrecur(np, buf, p+1, i+1, n-1);
	}
	return np;
}

char**
gennames(char **np, int n)
{
	char buf[100];
	buf[0] = 'E';
	return genrecur(np, buf, buf+1, 0, n);
}

int
flipproduct(char *digits)
{
	char *p, t;
	int done;
	int sign = 1;
	do {
		done = 1;
		for(p = digits; p[0] && p[1]; p++) {
			if(p[0] > p[1]) {
				t = p[0]; p[0] = p[1]; p[1] = t;
				sign = -sign;
				done = 0;
			}
		}
	} while(!done);
	return sign;
}

// need to support overlapped strings
void xstrcpy(char *s1, char *s2) { while(*s1++ = *s2++); }

char*
mul(char *e1, char *e2)
{
	int i;
	char sq[3], *p;
	int done;
	int sign;

	static char buf[100];
	buf[0] = ' ';
	buf[1] = 'E';
	sprintf(buf+2, "%s%s", e1+1, e2+1);

	sign = flipproduct(buf+2);

	sq[2] = '\0';
	do {
		done = 1;
		for(i = 0; i < VDIM; i++) {
			sq[0] = sq[1] = vnames[i];
			p = strstr(buf+2, sq);
			if(p) {
				sign *= sig[i];
				if(sign == 0)
					return "0";
				xstrcpy(p, p+2);
				done = 0;
			}
		}
	} while(!done);

	for(i = 0; i < DIM; i++)
		if(strcmp(names[i], buf+1) == 0) {
			sign *= signs[i];
			strcpy(buf+1, xnames[i]);
			break;
		}

	if(buf[2] == '\0')
		buf[1] = 'U';
	if(sign < 0)
		buf[0] = '-';
	return buf;
}

int
main()
{
	int i, j, k, n;
	i = 0;
	for(k = 0; k <= VDIM; k++) {
		nelts[k] = n = ncr(VDIM, k);
		while(n--)
			grade[i++] = k;
	}


	if(xnames[0] == NULL) {
		char **np;
		names[0] = "1";
		np = &names[1];
		for(i = 1; i <= VDIM; i++)
			np = gennames(np, i);
		memcpy(xnames, names, sizeof(char*)*DIM);
		for(i = 0; i < DIM; i++) signs[i] = 1;
	} else {
		for(i = 0; i < DIM; i++) {
			names[i] = strdup(xnames[i]);
			signs[i] = flipproduct(names[i]+1);
		}
	}


	for(i = 0; i < DIM; i++)
		printf("%d: %s %s%s\n", grade[i], names[i], signs[i] < 0 ? "-" : "+", xnames[i]);
	printf("\n");


	printf("enum { ");
	for(i = 1; i < DIM; i++)
		printf(" %s%s,", xnames[i], i==1 ? " = 1" : "");
	printf(" N };\n");
	printf("int grade[] = { ");
	for(i = 0; i < DIM; i++)
		printf(" %d,", grade[i]);
	printf(" };\n");

	printf("int elt[N][N] = {\n");
	for(i = 0; i < DIM; i++) {
		printf("\t{ ");
		for(j = 0; j < DIM; j++) {
			char *n = mul(xnames[i], xnames[j]);
			printf("%6s, ", n);
		}
		printf(" },\n");
	}
	printf("};\n");


	return 0;
}