Appendix:

Permuting a string

#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

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.

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