[alt.sources] Permutation generator

mday@iconsys.uucp (Matt Day) (10/13/90)

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

scotta@hpcuhd.HP.COM (Scott Anderson) (10/16/90)

    Here's one I did about 2 years ago for solving jumbles (in a pretty
gross way - see leading comment in program).  It doesn't use malloc and
uses pointers instead of indices.  The only minor disadvantage is that
dupes aren't eliminated.  I find it somewhat amusing how similar the
programs are though.

    Scott Anderson
    An RTEsian and proud of it...		Hewlett-Packard
						Data Systems Operation
    scotta@cup.hp.com				11000 Wolfe Rd.  MS 42UN
    408-447-5219				Cupertino, CA  95014
________________________________________________________________________

/* This program produces permutations of all of the strings passed to it.
 * To solve jumbles try:
 *	perm xxxxx | sort -u | tee temp | spell | sort | comm -13 - temp
 * where xxxxx is the scrambled word.
 */

#define SWAP(a, b)	ch = *(a); *(a) = *(b); *(b) = ch;

void perm(whole, partial)
    char *whole, *partial;
{
    register char *ptr, *next_partial, ch;

    if (!*partial) {
	puts(whole);
	return;
    }

    ptr = partial;
    next_partial = partial + 1;
    while (*ptr) {
	SWAP(partial, ptr);
	perm(whole, next_partial);
	SWAP(partial, ptr);
	ptr++;
    }
}

main (argc, argv)
    int argc;
    char **argv;
{
    int i;

    for (i=1; i<argc; i++)
	perm(argv[i], argv[i]);
}