Appendix:

Permuting a string

How do we permute a string (ie print out all the permutations of its letters)? Well, for a one-letter string we just print it out. For a two-letter string it's almost as easy, just print out the string and the then the string reversed (there are only two permutations).

How do you permute a three-letter string? Well, the permuations are

• The first letter followed by the permutions of the second and third letters.
• The second letter followed by the permutions of the first and third letters.
• The third letter followed by the permutions of the first and second letters.

So the algorithm is:

1. Keep the first letter constant and do all the permutations of the second and third letters (printing out the entire string each time).

2. Swap the original first and second letters of the string, and repeat step 1 for the new string.

3. Swap the original first and third letters of the string, and repeat step 1 for the new string.

General algorithm

For an N-letter string it's a bit like:

• for (i=0; i < N; ++i)
  1. Swap letters 0 and i.

  2. Permute letters 1 to N-1, printing out the entire string each time.

Notice the similary with mathematical proof by induction: if we know how to do it for the case N=1 and if knowing how to do it for any N allows us to do it for N+1 we can do it for all strictly positive N. The code looks like this:

#include <stdio.h>

//
// Permute a string from p to the end and print out each
// permutation starting from string_start (which never changes)
// Does not avoid duplicates
//
void permute(char *string_start, char *p) {
  char *swap;
  
  if (p[1] == 0) { // End of string - just print it
    printf("%s\n", string_start);
    return;
  }

// permute the string one shorter than this
  permute(string_start, p+1);
  
  // Go along the string, swapping each element in turn with p
  for(swap = p+1; *swap; ++swap) {
    char tmp = *swap;
    
    *swap = *p; // swap
    *p = tmp;
    permute(string_start, p+1);
    *p = *swap; // swap back
    *swap = tmp;
  }
}

int main(int argc, char **argv) {
  char string[8];

  while (1) {
    printf("String to permute?\n");
    if (scanf("%7s", string) < 1 )
      break;
    printf("Permutations of %s:\n", string);
    permute(string, string);
  }

  return 0;
}

Step through this code

This shows the two essential elements of recursion: a test to see if the function needs to call itself amd then the actual call (in this case inside a loop). It also shows that although the code is quite simple it's also a little subtle: why is the test on the loop exactly what it is? Why does the loop start off with the two pointers pointing to the same part of the string so that the 'swap' actually achieves nothing?

Recursion is simple but subtle.

Handling duplicate letters

The program above is fine when the input has no repeated letters (abcd) but prints out duplicates when there are (abcda). It's suprisingly easy to take care of this as we can see in this improved algorithm.

Clearing marked nodes

When dealing with nodes with loops we have to mark the nodes we have already visited to avoid infinite recursion. This is fine if we only ever want to ru the function once but if we wish to run the function again we must clear these marks. The general method is much the same as marking:

Check, Unmark, Recurse

void unmark(some_args) {
  if (node_has_not_been_visited)
    return;                          //Check 

  // Mark this node as NOT visited;  //Unmark 

  umark(some_other_args);            //Recurse
}

Flood fill example

In our flood fill example we may imaging that the number of pixels changes in some way: perhaps as new material is removed or deposited. We therefore need to reset our image before recalculating the islands. Note how we follow the order Check, Unmark, Recurse.

void unmark(char image[NY][NX], int x, int y) {
  if ( x < 0 || x >= NX || y < 0 || y >= NY 
       || image[y][x] == '*' || image[y][x] == ' ' ) 
    return ;                // Check
  
  image[y][x] = '*';        // Unmark
  unmark(image, x, y-1);    // Recurse
  unmark(image, x+1, y-1);
  unmark(image, x+1, y);
  unmark(image, x+1, y+1);
  unmark(image, x, y+1);
  unmark(image, x-1, y+1);
  unmark(image, x-1, y);
  unmark(image, x-1, y-1) ;
}

Connectivity of a mesh

Consider an array of nodes each of which is linked to each of its four neighbours to form a mesh. If we arbitrarily take the top edge of the mesh as our base we may then travel to the opposite (bottom) edge via a path made up of neighbouring nodes: we say that the top and bottom edges are connected:

0-0-0-0-0
| | | | |
0-0-0-0-0
| | | | |
0-0-0-0-0
| | | | |
0-0-0-0-0

Notes:

• There are no explicit bonds in this example: we just assume that any two adjacent nodes are automatically connected with each other.
• We are just using the "0" character as a conveniently shaped blob, they are not supposed to indicate that the array element representing the node will actually have the value zero. In our example it will have the value plus or minus one.

If we remove a few nodes the top and bottom edges will eventually become disconnected:

0-0-0-0-0      0     0-0            0-0            0-0   
| | | | |      |       |              |              |
0-0-0-0-0      0-0-0   0      0-0-0   0      0   0   0   
| | | | |  ->  |   |   |  ->  |   |   |  ->  |   |   |                 
0-0-0-0-0      0   0-0-0      0   0-0-0      0   0-0-0   
| | | | |      |   |   |      |              |                 
0-0-0-0-0      0-0-0   0      0-0            0-0      

Notice how in the third example the route doubles back on itself. In the third example we have removed one bond to disconnect the top and bottom edges. Also, we don't require that every top node be connected to every bottom node, just one.

Flood-fill can easily tell us if a mesh is connected in this way: we simply go along the top row flood-filling the nodes to one, then go along the bottom row lookign for nodes whose value is one. If we find one it's conected to the top, if we dont find any the msh has become disconnected (or has not yet become connected depending whether we are destroying or growing the mesh).

/*
 * Return 1 if the top row id connected to the bottom row
 * zero if it is not. We do this by flood-filling the top
 * row to ones and then go along the bottom row looking
 * for points cells that have been filled.
 */
int connected(int image[NX][NY]) {
  // Reset results of previous attempt
  for (int x = 0; x < NX; ++x)
    for (int y = 0; y < NY; ++y)
      if (image[x][y] != 0)
  image[x][y] = -1;

  // Flood-fill top row
    for (int x = 0; x < NX; ++x)
      if (image[x][0] == -1)
  floodfill(image, x, 0, 1);
 
    // Look at bottom row
    for (int x = 0; x < NX; ++x)
      if (image[x][NY-1] == 1)
  return 1;

    // Didn't find one, mesh not connected
    return 0;
}