Path: utzoo!utgpu!cs.utexas.edu!samsung!uunet!iconsys!mday
From: mday@iconsys.uucp (Matt Day)
Newsgroups: alt.sources
Subject: Permutation generator
Keywords: permutation
Message-ID: <1990Oct12.172633.8855@iconsys.uucp>
Date: 12 Oct 90 17:26:33 GMT
Organization: Sanyo/Icon International, Inc., Orem, Utah
Lines: 73

I've seen requests for a permutation generator several times in other groups,
so I thought I'd post my algorithm and see what everybody thinks.  Before I
wrote this version, I came up with a couple of algorithms that needed to
allocate a whole bunch of memory for an array, or needed to recurse a zillion
times.  This algorithm doesn't need to do either, therefore it's quite fast
and efficient.  I had a lot of fun working on this program, and I'd be happy
to discuss different methods that others may have.  I haven't included a
Makefile or anything, since such a simple program, so just save this article
off, delete my ramblings, and compile away (it should compile on about any
system).  Please bum my code and send patches, optimize, optimize!  Enjoy!

By the way, I have a version written in perfect ANSI C, if anyone cares..
---------------------------- Begin permute.c --------------------------------
/*
 * 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);
}
------------------------------- End permute.c --------------------------------
-- 
- Matthew T. Day, Sanyo/Icon, mday@iconsys.icon.com || uunet!iconsys!mday