Tag Archives: Algorithms

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

Finding the height of a binary tree recursively

The height of a node in a binary tree is simply the maximum of the height of its left and right subtrees, plus one.

This lends itself to a simple recursive algorithm for finding the height of a binary tree.

static int max(int a, int b)
{
    if (a >= b) {
        return a;
    }
    return b;
}

unsigned int binarytree_height_recursive(const btnode *node)
{
    unsigned int height = 0;
    if (node->left || node->right) {
        height = max(node->left ? binarytree_height_recursive(node->left) : 0,
                node->right ? binarytree_height_recursive(node->right) : 0) + 1;
    }
    return height;
}

unsigned int binarytree_height(const binarytree *tree)
{
	unsigned int height = 0;
	if (tree->root) {
		height = binarytree_height_recursive(tree->root);
	}
	return height;
}

Related

Counting nodes in a binary tree recursively

Introduction

The recursive structure of a binary tree makes it easy to count nodes recursively. There are 3 things we can count:

  • The total number of nodes
  • The number of leaf nodes
  • The number of internal nodes

Counting all nodes

The number of nodes in a binary tree is the number of nodes in the root’s left subtree, plus the number of nodes in its right subtree, plus one (for the root itself).

This lends itself to a simple recursive algorithm for counting the nodes in a binary tree.

unsigned int binarytree_count_recursive(const btnode *root)
{
    unsigned int count = 1;
    if (root->left != NULL) {
       count += binarytree_count_recursive(root->left);
    }
    if (root->right != NULL) {
        count += binarytree_count_recursive(root->right);
    }
    return count;
}

unsigned int binarytree_count(const binarytree *tree)
{
    unsigned int count = 0;
    if (tree->root != NULL) {
        count = binarytree_count_recursive(tree->root);
    }
    return count;
}

Counting leaf nodes

This is similar, except that we only return 1 if we are a leaf node. Otherwise, we recurse into the left and right subtrees and return the sum of the leaves in them.

unsigned int binarytree_count_leaves_recursive(const btnode *root)
{
    unsigned int count = 0;
    if (root->left == NULL && root->right == NULL) {
        count = 1;
    }
    else {
        if (root->left != NULL) {
		    count += binarytree_count_leaves_recursive(root->left);
	    }
        if (root->right != NULL) {
            count += binarytree_count_leaves_recursive(root->right);
        }
    }
	return count;
}

unsigned int binarytree_count_leaves(const binarytree *tree)
{
    unsigned int count = 0;
    if (tree->root != NULL) {
	    count = binarytree_count_leaves_recursive(tree->root);
    }
    return count;
}

Counting internal nodes

This is the counterpart of counting leaves. If we are an internal node, we count 1 for ourselves, then recurse into the left and right subtrees and sum the count of internal nodes in them.

unsigned int binarytree_count_internal_nodes_recursive(const btnode *root)
{
    unsigned int count = 0;
    if (root->left != NULL || root->right != NULL) {
        count = 1;
        if (root->left != NULL) {
		    count += binarytree_count_internal_nodes_recursive(root->left);
	    }
        if (root->right != NULL) {
            count += binarytree_count_internal_nodes_recursive(root->right);
        }
    }
	return count;
}

unsigned int binarytree_count_internal_nodes(const binarytree *tree)
{
    unsigned int count = 0;
    if (tree->root != NULL) {
	    count = binarytree_count_internal_nodes_recursive(tree->root);
    }
    return count;
}

Related