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; }