/*
 * permute - Generates all permutations of a given string.
 * Matthew T. Day (mday@iconsys.icon.com), 9/27/90.
 */

#include <stdio.h>

int len;
char tmp;

/* Simple macro for swapping two variables. */
#define swap(a, b) tmp = (a), (a) = (b), (b) = tmp

/*
 * The permutation generator.  This routine immediately recurses, passing
 * itself a copy of the string and its level of recursion, until it has
 * recursed to a depth equal to the length of the string.  At that point it
 * loops, printing the string and shifting to the left the character located
 * in the array offset by the recursion level.  When the character being
 * shifted reaches the beginning of the string, it drops back to the
 * previous level of recursion.
 */
void permute(string, index)
register char *string;
register int index;
{
	register int level = index, printing = !string[index + 1];
	register char *copy;

	if (!(copy = (char *) malloc(len * sizeof(char) + 1))) {
		(void) fputs("Error: Out of memory.", stderr);
		exit(1);
	}

	(void) strcpy(copy, string);

	do {
		if (printing) (void) puts(copy);
		else permute(copy, level + 1);
		if (index) swap(copy[index], copy[index - 1]);
	} while (index--);
}

void main(argc, argv)
int argc;
char **argv;
{
	if (argc != 2) {
		(void) fputs("Usage: permute string\n", stderr);
		exit(1);
	}

	len = strlen(argv[1]);
	permute(argv[1], 0);

	exit(0);
}