Comments and questions to John Rowe.

Recursion example: permuting a string

John Rowe.

[Aside: if scanf allowed me to enter a zero-length string what would happen to the program above? Fortunately it doesn't but if it did how would I take care of that problem?]

A better program

[You don't have to worry about this if you don't want to!]

:

#include <stdio.h>

void permute(char *string_start, char *p) {
  
  if (*(p+1) == 0) {
     printf("%s\n", string_start);
  }
  else {
   char *swap;
    /* Go along the string, in turn swapping each element with p */
    for(swap = p; *swap; ++swap) {
      char *same;
      /* Check we have not already done an identical permutation */
      for(same = p; *same != *swap; ++same) {
      }
      if (same == swap) {
  char tmp = *swap;
  *swap = *p;
  *p = tmp;
  permute(string_start, p+1);
  *p = *swap;
  *swap = tmp;
      }
    }
  }
}

The difference is in the loop:

      for(same = p; *same != *swap; ++same) {
      }

The first thing to note is that an empty loop is quite legal - we are just looking for the first occurance of the character *swap in the string (remember that swap is a pointer to a character inside the string which starts at p). If the loop stops before swap we know that we have already called permute with an identical string so we don't call it again.

Note in this code the difference between two pointers being the same (they point to the same place in memory) and the values they point to being the same (which is true either if they point to the same place in memory or the same data value is stored in two different places in the memory). Log in