/*
 * Permute the letters of a word.
 *
 * Usage: permword word
 *
 * There are n! permutations of a word with n letters. E.g., 10
 * letters means 3,628,800 permutations. While those 10! take only
 * half a second to generate, time increases quickly: 11 letters: 6
 * seconds; 12 letters: 1 minute 15 seconds; 13 letters: 18 minutes;
 * etc.
 *
 * This program does not check if some letters are the same. E.g.,
 * "dada" has four letters and thus 24 permutations, but in fact only
 * 6 different ones. Use "permword dada | sort -u" to weed out the
 * duplicates.
 *
 * Author: Bert Bos <bert@w3.org>
 * Created: 29 June 1999
 * Version: $Id: permword.c,v 1.1 2015/08/15 00:24:15 bbos Exp $
 *
 * This is Open Source software, see http://www.w3.org/Consortium/Legal/
 *
 * Copyright © 1995-2015 World Wide Web Consortium
 * See http://www.w3.org/Consortium/Legal/2002/copyright-software-20021231
 */

/*
#include <sys/mman.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <fcntl.h>
*/
#include <string.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>



/* fatal -- print message and exit */
static void fatal(char *s, char *t) {fprintf(stderr, "%s: %s", s, t); exit(1);}

/* syserr -- print system error and exit */
static void syserr(char *msg) {fatal(msg, strerror(errno));}

/* swap -- swap two letters */
static inline void swap(char *a, char *b) {char h; h = *a; *a = *b; *b = h;}

/* permute -- recursively print all permutations of word[n..] */
static void permute(char word[], int n)
{
  int i;

  if (!word[n]) {
    /* Write the current set of letters */
    for (i = 0; word[i]; i++) if (putchar(word[i]) < 0) syserr("permute");
    if (putchar('\n') < 0) syserr("permute");
  } else {
    /* Put letter n at all possible positions */
    permute(word, n + 1);
    for (i = n + 1; word[i]; i++) {
      swap(&word[n], &word[i]);
      permute(word, n + 1);
      swap(&word[n], &word[i]);
    }
  }
}

/* main -- read lines, permute and write them */
int main(int argc, char *argv[])
{
  if (argc != 2) fatal("Usage", "permword word\n");
  permute(argv[1], 0);
  return 0;
}