A simple program that counts the number of monotonic, dependent, and distinct functions of 4 boolean variables. I wrote this for a little mini-contest for my Digital Logic Design class in 2010. There was only one other student who solved it, and his Java code was wayyy longer and uglier. As I thought this was a fairly elegant little program, I'm…

gistfile1.c

#include <stdio.h>

const int mask[4] = { 0x5555, 0x3333, 0x0F0F, 0x00FF };

int count_table(int *table, char *lbl) {
	int count, x;

	for (count = x = 0; x < 1<<16; x++)
		count += table[x];

	printf("%s: %i\n", lbl, count);
}

int main(void) {
	int count, x, y, z, i, j, idx[4], t[4];
	int table[1<<16];

	/* Mark every possible function of four variables as valid, we will weed
	 * out the bad ones below. */
	for (x = 0; x < 1<<16; x++)
		table[x] = 1;

	for (x = 0; x < 1<<4; x++) {
		/* x holds the boolean arguments to a function f in its bits.
		 *
		 * Traverse all of the subsets of x. Each subset has the property that
		 * the set of boolean variables given by that bit pattern is <= x. */
		y = 0;
		do {
			y = (y - x) & x;

			/* Exclude all of the functions that have f(y) > f(x) */
			for (i = 0; i < 1<<16; i++)
				if ((i>>y & 1) && !(i>>x & 1))
					table[i] = 0;
		} while (y);
	}

	/* Count how many functions are left => nb. of monotonic functions */
	count_table(table, "Monotonic");

	/* Count how many functions depend on each variable. */
	for (x = 0; x < 1<<16; x++) {
		if (table[x]) {
			/* Each function that doesn't depend on a variable will have
			 * the same values if the variable is 0 or 1. We can do this
			 * with a quick mask on the output of f, one for each bit. */
			for (y = 0; y < 4; y++)
				if ((x & mask[y]) == (x >> (1 << y) & mask[y]))
					table[x] = 0;
		}
	}

	/* Count how many functions are left => nb. of dependent functions */
	count_table(table, "Dependent");

	/* Count how many functions remain after removing permutations. */
	for (x = 0; x < 1<<16; x++) {
		if (table[x]) {
			for (y = 0; y < 4; y++)
				idx[y] = y;
			/* Permutation algorithm from wiki. */
			while (1) {
				for (y = 2; y >= 0; y--)
					if (idx[y] < idx[y + 1])
						break;
				if (y == -1)
					break;
				for (z = 3; z >= 0; z--)
					if (idx[z] > idx[y])
						break;
				i = idx[y];
				idx[y] = idx[z];
				idx[z] = i;

				for (i = y+1, j = 3; i < j; i++, j--) {
					z = idx[i];
					idx[i] = idx[j];
					idx[j] = z;
				}

				i = 0;
				/* y: original index, j: transformed index */
				for (y = 0; y < 1<<4; y++) {
					j = 0;
					/* x: original fn, i: transformed fn */
					for (z = 0; z < 4; z++)
						j |= (y >> z & 1) << idx[z];

					i |= (x >> y & 1) << j;
				}

				/* Remove everything but the smallest permutation. */
				if (i > x)
					table[i] = 0;
			}
		}
	}

	/* Count how many functions are left => nb. of distinct functions */
	count_table(table, "Distinct");
}