constant space string permutation

perms.c

/*
 * perms.c
 *
 * [email protected]
 *
 * read strings from stdin and print the permutations in lex order.
 *
 * permutations are computed using constant space.
 *
 * algorithm transliterated to C from TAOCP, Vol 4A, Part 1
 * (0-201-03804-8), pp. 319
 *
 * gcc -Wall -Wextra -pedantic -std=gnu11 -o perms perms.c
 * clang -Weverything -std=gnu11 -o perms perms.c
 *
 * $ echo 'test' | ./perms
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <errno.h>

/* https://en.wikipedia.org/wiki/XOR_swap_algorithm */
#define SWAP(a,b) (a=a^b);(b=a^b);(a=a^b)

void printPerms(const char * const source);

int main() {
  while(!feof(stdin)) {
    char * userStr = NULL;
    int scanRet = scanf("%ms", &userStr);

    if(scanRet == EOF) {
      if(errno != 0) {
        fprintf(stderr, "failed to read and match a string: %s\n",
          strerror(errno));
      }

      exit(scanRet);
    }

    printPerms(userStr);
    free(userStr);
  }

  return 0;
}

/* qsort comparator for chars */
static int comparCh(const void * chOne, const void * chTwo) {
  return (*(char *)(chOne)) > (*(char *)(chTwo));
}

void printPerms(const char * const source) {
  const size_t n = strlen(source);

  if(n < 2) return;

  char * a = strdup(source);

  /* L1: sort and enumerate */
  qsort(a, n, 1, comparCh);

  while(true) {
    printf("%s\n", a);
    /* L2: find j */

    /* set j to index of second to last character in a */
    int j = ((signed int) n) - 1 - 1;

    /* if the penultimate character is already in order...*/
    if(a[j] >= a[j+1]) {

      /* search left until you find one that isn't */
      do {
        --j;
      } while(j >= 0 && a[j] >= a[j+1]);
    }

    /* and terminate if we ran out of characters. */
    if(j == -1) {
      free(a);
      return;
    }

    /* L3: increase aj */

    /* set l to the index of the last character in a */
    int l = (int) n - 1;

    /* if the jth character is less than the last... */
    if(a[j] >= a[l]) {

      /* search left until it isn't */
      do {
        --l;
      } while(l >= 0 && a[j] >= a[l]);
    }

    SWAP(a[j], a[l]);

    /* L4: reverse a[j+1] ... n, inclusive */
    for(int k = j + 1, m = (int) n - 1; k < m; ++k, --m) {
      SWAP(a[k], a[m]);
    }
  }
}