Physics and Astronomy |
Back to top
On this page
Contents Appendix:The occasional appendices and optional examples in this module are for advanced material that you will not need for this module. They are intended for enthusiastic students who are interested in going further in programming for its own sake. Permuting a stringHow 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
General algorithmFor an N-letter string it's a bit like:
#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; } 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 lettersThe 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 nodesWhen 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, Recursevoid 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 exampleIn 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 meshConsider 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:
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; } |