Character String Permutation
David J. McVicar
mcvic at prcrs.UUCP
Thu Sep 14 10:52:26 AEST 1989
I have wrestled with this annoying algorithm long enough. Can anyone
on the net lend assitance?
Here's what I'm trying to do...
I have written a small C program to list out all the permutations
of a given text string.
(ex. unix unxi uinx uixn uxni uxin nuix nuxi niux nixu nxui nxiu iunx iuxn inux
inxu ixun ixnu xuni xuin xnui xniu xiun xinu)
But, when a string containing repeating characters is entered, I would like
to output only unique strings.
(ex. foo foo ofo oof ofo oof <= my current program
foo ofo oof <= desired output)
An obvious solution for UNIX types is to pipe the output into sort -u, but for
long character strings this would be prohibitive. Is there any way, given
the nature of my solution below, to determine repeats in permutations on the
fly?
Thanks in advance for any help with this one.
Dave McVicar (uunet!prcrs!mcvic)
====== The program below will print out all permutations, with repeats =====
#include <stdio.h>
#define COLWID 80
extern char *malloc();
int *pa;
char *str;
char *outbuf;
int size;
int func()
{
static int col = 0;
register int i;
for(i=0; i < size; ++i)
outbuf[i] = str[pa[i]];
outbuf[i] = '\0';
if ((col += (size + 1)) >= COLWID) {
printf("\n");
col = size + 1;
}
printf("%s ", outbuf);
return (1);
} /* end func() subroutine */
int
doperm(offset, func)
register int offset;
int (*func)();
{
int index;
int k, skip;
if (offset == size)
return( (*func)() );
for (index = 0; index < size; ++index) {
for (k = 0; k < offset; ++k)
if (skip = (index == pa[k]))
break;
if (skip)
continue;
pa[offset] = index;
doperm(offset + 1, func);
}
return;
}
main(argc, argv)
int argc;
char **argv;
{
register int i,j;
if (argc == 1) {
fprintf (stderr, "usage: permute <string>\n\n");
exit (2);
}
str = argv[1];
size = strlen(str);
if (size == 0)
exit(0);
else if (size == 1) {
printf("%s\n", argv[1]);
exit(0);
}
pa = (int *)malloc(size * sizeof(int));
outbuf = malloc(size + 1);
for (i = 0; i < size; ++i) {
pa[0] = i;
for (j = 1; j < size; ++j)
pa[j] = 0;
doperm(1, func);
}
free(pa);
free(outbuf);
exit(0);
}
======================
More information about the Comp.lang.c
mailing list