# Permutations

The permutations of a set are the ways of arranging its elements.

For example, there are 24 permutations of a set of 4 elements:

[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 1, 2]
[0, 3, 2, 1]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 0, 2]
[1, 3, 2, 0]
[2, 0, 1, 3]
[2, 0, 3, 1]
[2, 1, 0, 3]
[2, 1, 3, 0]
[2, 3, 0, 1]
[2, 3, 1, 0]
[3, 0, 1, 2]
[3, 0, 2, 1]
[3, 1, 0, 2]
[3, 1, 2, 0]
[3, 2, 0, 1]
[3, 2, 1, 0]


To find the next permutation of an array ar:

1. Find the highest index, i1 such that ar[i1] is the first of a pair of elements in ascending order.
If there isn’t one, the sequence is the highest permutation, so reverse the whole thing to begin again.

2. Find the highest index i2, such that i2 > i1 and ar[i2] > ar[i1].
3. Swap ar[i1] and ar[i2].
4. The elements from ar[i1 + 1] to the end are now in descending order (a later permutation), so reverse them.
static void swap(unsigned int *ar, unsigned int first, unsigned int second)
{
unsigned int temp = ar[first];
ar[first] = ar[second];
ar[second] = temp;
}

static void reverse(unsigned int *ar, size_t len)
{
unsigned int i, j;

for (i = 0, j = len - 1; i < j; i++, j--) {
swap(ar, i, j);
}
}

unsigned int next_permutation(unsigned int *ar, size_t len)
{
unsigned int i1, i2;
unsigned int result = 0;

/* Find the rightmost element that is the first in a pair in ascending order */
for (i1 = len - 2, i2 = len - 1; ar[i2] <= ar[i1] && i1 != 0; i1--, i2--);
if (ar[i2] <= ar[i1]) {
reverse(ar, len);
}
else {
/* Find the rightmost element to the right of i1 that is greater than ar[i1] */
for (i2 = len - 1; i2 > i1 && ar[i2] <= ar[i1]; i2--);
/* Swap it with the first one */
swap(ar, i1, i2);
/* Reverse the remainder */
reverse(ar + i1 + 1, len - i1 - 1);
result = 1;
}
return result;
}


# 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 {
for (i = 0; i < n; i++) {
ar[i] = 0;
}
result = 0;
}
return result;
}


# Circular linked list in C

A circular linked list is a linked list in which the head node’s previous pointer points to the tail node, and the tail node’s next pointer points to the head node. This means that the list only needs to keep track of one pointer for both head and tail.

Looping over a circular linked list is slightly different from looping over an ordinary linked list because there is no NULL node to detect, and instead you are trying to get back to where you started. There are 2 methods of doing this.

Method 1: Use a do loop

void iterate1(const circularlist *list)
{
if (node != NULL) {
do {
printf("%s\n", (const char*)node->data);
node = node->next;
}
}



Method 2: Use a counter

void iterate2(const circularlist *list)
{
cnode *node;
unsigned int i;
for (i = 0, node = list->head; i < list->count; i++, node = node->next) {
printf("%s\n", (const char*)node->data);
}
}


#ifndef CIRCULARLIST_H
#define CIRCULARLIST_H

struct cnode {
struct cnode * next;
struct cnode * previous;
void * data;
};
typedef struct cnode cnode;

struct circularlist {
unsigned int count;
};
typedef struct circularlist circularlist;

typedef void (*circularlist_forfn)(void *);

circularlist * circularlist_create(void);
void circularlist_delete(circularlist * list);

void circularlist_add_tail(circularlist * list, void * data);
void * circularlist_remove_tail(circularlist * list);
void * circularlist_remove_node(circularlist * list, cnode * node);
void circularlist_empty(circularlist * list);

void circularlist_insert_before(circularlist * list, cnode * node, void * data);
void circularlist_insert_after(circularlist * list, cnode * node, void * data);

void circularlist_for_each(const circularlist * list, circularlist_forfn fun);
unsigned int circularlist_get_count(const circularlist * list);

#endif /* CIRCULARLIST_H */


Here is the implementation

#include <stdlib.h>

#include <circularlist.h>

static cnode * cnode_create(void * data)
{
cnode * node = malloc(sizeof(cnode));
if(node) {
node->next = node;
node->previous = node;
node->data = data;
}

return node;
}

static void cnode_delete(cnode * node)
{
free(node);
}

circularlist * circularlist_create(void)
{
circularlist * list = malloc(sizeof(circularlist));
if (list) {
list->count = 0;
}

return list;
}

void circularlist_delete(circularlist * list)
{
if (list) {
circularlist_empty(list);
free(list);
}
}

{
}

void circularlist_add_tail(circularlist * list, void * data)
{
}

{
}

void * circularlist_remove_tail(circularlist * list)
{
void * data = NULL;
}
return data;
}

void * circularlist_remove_node(circularlist * list, cnode * node)
{
void * data = NULL;
if (list->count > 0) {
if (node != node->next) { /* Or, list->count > 1 */
node->next->previous = node->previous;
node->previous->next = node->next;
}
else {
/* Removing the last element */
}
data = node->data;
cnode_delete(node);
list->count--;
}
return data;
}

void circularlist_empty(circularlist * list)
{
while (circularlist_remove_tail(list) != NULL);
}

void circularlist_insert_before(circularlist * list, cnode * node, void * data)
{
cnode * newnode = cnode_create(data);

if (newnode) {
if (list->count > 0) {
newnode->next = node;
newnode->previous = node->previous;
newnode->previous->next = newnode;
node->previous = newnode;
}
else {
/* Adding the first element */
}
list->count++;
}
}

void circularlist_insert_after(circularlist * list, cnode * node, void * data)
{
circularlist_insert_before(list, node->next, data);
}

void circularlist_for_each(const circularlist * list, circularlist_forfn fun)
{

if (node != NULL) {
do {
fun(node->data);
node = node->next;
}
}

unsigned int circularlist_get_count(const circularlist *list)
{
return list->count;
}


Here is a test program

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

#include <circularlist.h>

int main(void)
{
char * elements[] = {"A", "B", "C", "D", "E", "F"};
const unsigned int n = sizeof(elements) / sizeof(const char*);
circularlist * list;
unsigned int i;
cnode * node;
unsigned int removed = 0, added = 0;

list = circularlist_create();
if (list) {
/* Populate the list */
for (i = 0; i < n; i++) {
}

/* Remove "C" */
do {
if (strcmp((const char*)node->data, "C") == 0) {
circularlist_remove_node(list, node);
removed = 1;
}
else {
node = node->next;
}
} while (node != list->head && !removed);

/* Add "X" and "Y" either side of "D" */
do {
if (strcmp((const char*)node->data, "D") == 0) {
circularlist_insert_before(list, node, "X");
circularlist_insert_after(list, node, "Y");
}
else {
node = node->next;
}

/* Print */
printf("Count is %d\n", circularlist_get_count(list));
circularlist_for_each(list, (circularlist_forfn)puts);

circularlist_delete(list);
}
return 0;
}


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


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


# Select server for windows

This is the Windows version of the Select Server.

#ifndef WIN32_LEAN_AND_MEAN
#define WIN32_LEAN_AND_MEAN
#endif

#include <stdio.h>
#include <windows.h>
#include <winsock2.h>
#include <ws2tcpip.h>

#define PORT    "32001" /* Port to listen on */
#define BACKLOG 10		/* Passed to listen() */

void handle(SOCKET newsock, fd_set *set)
{
/* send(), recv(), closesocket() */
/* Call FD_CLR(newsock, set) on disconnection */
}

int main(void)
{
WORD wVersion = MAKEWORD(2, 2);
int iResult;
SOCKET sock;
fd_set socks;
SOCKET maxsock;
int reuseaddr = 1; /* True */

/* Initialise Winsock */
if (iResult = (WSAStartup(wVersion, &wsaData)) != 0) {
printf("WSAStartup failed: %d\n", iResult);
return 1;
}

/* Get the address info */
ZeroMemory(&hints, sizeof hints);
hints.ai_family = AF_INET;
hints.ai_socktype = SOCK_STREAM;
if (getaddrinfo(NULL, PORT, &hints, &res) != 0) {
WSACleanup();
return 1;
}

/* Create the socket */
sock = socket(res->ai_family, res->ai_socktype, res->ai_protocol);
if (sock == -1) {
perror("socket");
WSACleanup();
return 1;
}

/* Enable the socket to reuse the address */
sizeof(int)) == SOCKET_ERROR) {
perror("setsockopt");
WSACleanup();
return 1;
}

/* Bind to the address */
perror("bind");
WSACleanup();
return 1;
}

/* Listen */
if (listen(sock, BACKLOG) == SOCKET_ERROR) {
perror("listen");
WSACleanup();
return 1;
}

/* Set up the fd_set */
FD_ZERO(&socks);
FD_SET(sock, &socks);
maxsock = sock;

/* Main loop */
while (1) {
SOCKET s;
if (select(maxsock + 1, &readsocks, NULL, NULL, NULL) == SOCKET_ERROR) {
perror("select");
WSACleanup();
return 1;
}
for (s = 0; s <= maxsock; s++) {
if (s == sock) {
/* New connection */
SOCKET newsock;

if (newsock == INVALID_SOCKET) {
perror("accept");
}
else {
printf("Got a connection from %s on port %d\n",
FD_SET(newsock, &socks);
if (newsock > maxsock) {
maxsock = newsock;
}
}
}
else {
/* Handle read or disconnection */
handle(s, &socks);
}
}
}
}

/* Clean up */
closesocket(sock);
WSACleanup();

return 0;
}


# Select server

This server uses the select function to determine when sockets are ready for reading, and when clients have disconnected. It is not as fast as forking or using threads, and cannot exploit multi-cores, but is less resource intensive, and so will scale up to far more connections.

In order to prevent the handling of individual clients from starving others, it may necessary to limit how much data is read per client in response to each select call. Additionally, this example assumes that calls to recv will not block. If they can block, it may be necessary to put the socket in non-blocking mode using fcntl with the F_SETFL command and the O_NONBLOCK flag.

#include <stdio.h>
#include <string.h> /* memset() */
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <netdb.h>

#define PORT    "32001" /* Port to listen on */
#define BACKLOG     10  /* Passed to listen() */

void handle(int newsock, fd_set *set)
{
/* send(), recv(), close() */
/* Call FD_CLR(newsock, set) on disconnection */
}

int main(void)
{
int sock;
fd_set socks;
int maxsock;
int reuseaddr = 1; /* True */

/* Get the address info */
memset(&hints, 0, sizeof hints);
hints.ai_family = AF_INET;
hints.ai_socktype = SOCK_STREAM;
if (getaddrinfo(NULL, PORT, &hints, &res) != 0) {
return 1;
}

/* Create the socket */
sock = socket(res->ai_family, res->ai_socktype, res->ai_protocol);
if (sock == -1) {
perror("socket");
return 1;
}

/* Enable the socket to reuse the address */
perror("setsockopt");
return 1;
}

/* Bind to the address */
perror("bind");
return 1;
}

/* Listen */
if (listen(sock, BACKLOG) == -1) {
perror("listen");
return 1;
}

/* Set up the fd_set */
FD_ZERO(&socks);
FD_SET(sock, &socks);
maxsock = sock;

/* Main loop */
while (1) {
unsigned int s;
if (select(maxsock + 1, &readsocks, NULL, NULL, NULL) == -1) {
perror("select");
return 1;
}
for (s = 0; s <= maxsock; s++) {
if (s == sock) {
/* New connection */
int newsock;
if (newsock == -1) {
perror("accept");
}
else {
printf("Got a connection from %s on port %d\n",
FD_SET(newsock, &socks);
if (newsock > maxsock) {
maxsock = newsock;
}
}
}
else {
/* Handle read or disconnection */
handle(s, &socks);
}
}
}

}

close(sock);

return 0;
}