Tag Archives: Mathematics

Cartesian Product

The cartesian product of n sets is the set of ordered n-tuples containing one element from each set.

For example, the cartesian product of the sets {a, b}, {p, q, r} and {w, x, y, z} is:

[a, p, w]
[a, p, x]
[a, p, y]
[a, p, z]
[a, q, w]
[a, q, x]
[a, q, y]
[a, q, z]
[a, r, w]
[a, r, x]
[a, r, y]
[a, r, z]
[b, p, w]
[b, p, x]
[b, p, y]
[b, p, z]
[b, q, w]
[b, q, x]
[b, q, y]
[b, q, z]
[b, r, w]
[b, r, x]
[b, r, y]
[b, r, z]

The algorithm uses an array of n integers. Each number in the array represents the index number within the corresponding set of that element.

The algorithm then simply needs to count upwards from n zeroes, with the cardinality of each set determining when a digit rolls over.

For example, these are the correspondences between the array and the n-tuple for the sets in the example:

[0, 0, 0] = [a, p, w]
[0, 0, 1] = [a, p, x]
[0, 0, 2] = [a, p, y]
[0, 0, 3] = [a, p, z]
[0, 1, 0] = [a, q, w]
[0, 1, 1] = [a, q, x]
[0, 1, 2] = [a, q, y]
[0, 1, 3] = [a, q, z]
[0, 2, 0] = [a, r, w]
[0, 2, 1] = [a, r, x]
[0, 2, 2] = [a, r, y]
[0, 2, 3] = [a, r, z]
[1, 0, 0] = [b, p, w]
[1, 0, 1] = [b, p, x]
[1, 0, 2] = [b, p, y]
[1, 0, 3] = [b, p, z]
[1, 1, 0] = [b, q, w]
[1, 1, 1] = [b, q, x]
[1, 1, 2] = [b, q, y]
[1, 1, 3] = [b, q, z]
[1, 2, 0] = [b, r, w]
[1, 2, 1] = [b, r, x]
[1, 2, 2] = [b, r, y]
[1, 2, 3] = [b, r, z]
unsigned int next_n_tuple(unsigned int *ar, size_t len, const size_t *sizes)
{
	unsigned int changed = 0;
	unsigned int finished = 0;
	unsigned int i;

	for (i = len - 1; !changed && !finished; i--) {
		if (ar[i] < sizes[i] - 1) {
			/* Increment */
			ar[i]++;
			changed = 1;
		}
		else {
			/* Roll over */
			ar[i] = 0;
		}
		finished = i == 0;
	}

	return changed;
}	

Partitions

A partition of a set is a division of it into disjoint subsets whose union is the set itself.

For example, the partitions of the set {a, b, c, d} are:

{{a, b, c, d}}
{{a, b, c}, {d}}
{{a, b, d}, {c}}
{{a, b}, {c, d}}
{{a, b}, {c}, {d}}
{{a, c, d}, {b}}
{{a, c}, {b, d}}
{{a, c}, {b}, {d}}
{{a, d}, {b, c}}
{{a}, {b, c, d}}
{{a}, {b, c}, {d}}
{{a, d}, {b}, {c}}
{{a}, {b, d}, {c}}
{{a}, {b}, {c, d}}
{{a}, {b}, {c}, {d}}

The scheme I am using is as follows: a partition is represented by an array of the same size as the set, and each element in the array is an integer specifying the subset in the partition in which the corresponding element occurs. For example, the array [0, 0, 0, 0] indicates that every element occurs in set 0, the first set, i.e., the partition {{a, b, c, d}}, while the array [0, 1, 2, 3] puts every element in its own set, i.e., the partition {{a}, {b}, {c}, {d}}.

The correspondences for the partitions of a 4-set are as follows:

[0, 0, 0, 0] = {{a, b, c, d}}
[0, 0, 0, 1] = {{a, b, c}, {d}}
[0, 0, 1, 0] = {{a, b, d}, {c}}
[0, 0, 1, 1] = {{a, b}, {c, d}}
[0, 0, 1, 2] = {{a, b}, {c}, {d}}
[0, 1, 0, 0] = {{a, c, d}, {b}}
[0, 1, 0, 1] = {{a, c}, {b, d}}
[0, 1, 0, 2] = {{a, c}, {b}, {d}}
[0, 1, 1, 0] = {{a, d}, {b, c}}
[0, 1, 1, 1] = {{a}, {b, c, d}}
[0, 1, 1, 2] = {{a}, {b, c}, {d}}
[0, 1, 2, 0] = {{a, d}, {b}, {c}}
[0, 1, 2, 1] = {{a}, {b, d}, {c}}
[0, 1, 2, 2] = {{a}, {b}, {c, d}}
[0, 1, 2, 3] = {{a}, {b}, {c}, {d}}

Having established how to represent partitions, the algorithm simply needs to produce the arrays shown above. At each step:

  1. Find the rightmost element that is no more than any element to its left
  2. Increment it
  3. Set all of the elements after it to 0
unsigned int next_partition(unsigned int *ar, size_t len)
{	
	unsigned int result = 0;
	if (ar[len - 1] < len - 1) {
		unsigned int i;
		unsigned int finished = 0;
		unsigned int changed = 0;
		/* Find the rightmost element no more than the other elements */
		for (i = len - 1; !finished && !changed; i--) {
			unsigned int j, max = 0;
			/* Find the highest element to the left of this one */
			for (j = 0; j < i; j++) {
				if (ar[j] > max) {
					max = ar[j];
				}
			}
			if (ar[i] <= max) {
				/* Increment */
				ar[i]++;
				changed = 1;
				/* Set the following elements to 0 */
				for (j = i + 1; j < len; j++) {
					ar[j] = 0;
				}
			}
			finished = i == 1;
		}
		result = 1;
	}

	return result;
}

Subsets using Gray codes

When calculations are being performed on each element of the power set, it can be advantageous if each set differs from its predecessor by as few elements as possible. One can produce the subsets in order such that each subset differs from its predecessor by only one element. The characteristic vectors of sets in this order are called Gray codes.

These are the Gray codes in order for a set of 3 elements:

[0, 0, 0]
[1, 0, 0]
[1, 1, 0]
[0, 1, 0]
[0, 1, 1]
[1, 1, 1]
[1, 0, 1]
[0, 0, 1]

They correspond to the following subsets. Notice how each subset differs from its predecessor by only 1 element:

{}
{a}
{a, b}
{b}
{b, c}
{a, b, c}
{a, c}
{c}

In order to go from one Gray code to its successor, it is necessary to find which single value in the array to change from 1 to 0, or vice-versa.

The rules for finding the index of this element j are based on the number of 1s in the current code, k, as follows:

  • If k is even, then j = 0
  • If k is odd, then j is the index of the first cell that follows the first 1
unsigned int next_subset_gray(unsigned int *ar, size_t n)
{
    /* Find the number of 1s, and the first 1 */
	unsigned int i;
    unsigned int k = 0;
    int first_1 = -1;
    unsigned int finished = 0;
    for (i = 0; i < n; i++) {
        if (ar[i] == 1) {
            k++;
            if (first_1 == -1) {
                first_1 = i;
            }
        }
    }
    /* Flip the relevant digit */
    if (k % 2 == 0) {
        /* First digit */
        ar[0] ^= 1;
    }
    else if (first_1 < n - 1) {
        /* Digit after the first 1 */
        ar[first_1 + 1] ^= 1;
    }
    else {
        /* Last digit */
        ar[n - 1] = 0;
        finished = 1;
    }
    return finished == 0;
}

Subsets

The set of all subsets of a set is called the power set.

For example, the power set of the set {a, b, c} consists of the sets:

{}
{a}
{b}
{c}
{a, b}
{a, c}
{b, c}
{a, b, c}

Note that:

  • The empty set {} is in the power set
  • The set itself is in the power set

The set of all subsets of a particular size, or k-subsets, are combinations.

A subset can be represented as an array of boolean values of the same size as the set, called a characteristic vector. Each boolean value indicates whether the corresponding element in the set is present or absent in the subset.

This gives following correspondences for the set {a, b, c}:

[0, 0, 0] = {}
[1, 0, 0] = {a}
[0, 1, 0] = {b}
[0, 0, 1] = {c}
[1, 1, 0] = {a, b}
[1, 0, 1] = {a, c}
[0, 1, 1] = {b, c}
[1, 1, 1] = {a, b, c}

The algorithm then simply needs to produce the arrays shown above. Observing how they change, one can derive the following algorithm:

  • Find the rightmost 1 with a 0 on its right. If it exists:
    1. Move it one cell to the right
    2. Move all of the 1s on its right, which are packed on the right hand side, to the cells immediately behind it
  • Otherwise, If all of the 1s are on the right hand side and ar[0] is 0, add another 1 and move the other 1s immediately behind it
  • Otherwise, all subsets have been produced, so return the array to its starting arrangement of all 0s
unsigned int next_subset(unsigned int *ar, size_t n)
{
	int i, ones = 0;
	unsigned int found = 0;
	unsigned int result = 1;

	/* Find the rightmost 1 with a 0 on its right, or the number of 1s */
	for (i = n - 2; !found && i >= 0; i--) {
		found = ar[i] == 1 && ar[i + 1] == 0;
		ones += ar[i + 1] == 1;
	}
	if (found) {
		/* Move the 1 right */
		ar[++i] = 0;
		ar[++i] = 1;
        /* Pack the 1s to its right immediately behind it */
        i++;
        for (; i < n; i++, ones--) {
            if (ones > 0) {
                ar[i] = 1;
            }
            else {
                ar[i] = 0;
            }
        }
	}
	else  if (ar[0] == 0) {
		/* Add a new 1 and place them all at the beginning */
		for (i = 0; i < n; i++) {
			if (i < ones + 1) {
				ar[i] = 1;
			}
			else {
				ar[i] = 0;
			}
		}
	}
	else {
		/* Finished, return to the starting arrangement */
		for (i = 0; i < n; i++) {
			ar[i] = 0;
		}
		result = 0;
	}
	return result;
}