function to permute a string

[Yuan Zhong]

hello all, not sure if it's appropriate to post here. If not, I am sorry
and please direct me to the right groups. Thanks.


I write this function to permute a string. e.g. if the input string is
"abc", I am expecting to see the output: "abc", "acb", "bac", "bca",
"cab", "cba"
there is n! output for a string of size(n). Here is my code fragment,
Can anyone points out how to improve my code so that I get the right
output. You can see the current input for just running the code. I believe
the algorithm is correct. Thanks.


void permute(char *s)
{
int i,j,k;
char str[100];

if (strlen(s) <= 1)
printf("%s\n", s);
else {
for (i=0; i< strlen(s); i++) {
memset(str, 0, sizeof(str));
printf("%c",s);
strcpy(str,s);
for (j=i; j<strlen(s); j++)
str[j] = str[j+1];

str[strlen(s)-1] = 0;
permute(str);
}
}
}

 

[Nick Austin]

hello all, not sure if it's appropriate to post here. If not, I am sorry
and please direct me to the right groups. Thanks.


I write this function to permute a string. e.g. if the input string is
"abc", I am expecting to see the output: "abc", "acb", "bac", "bca",
"cab", "cba"
there is n! output for a string of size(n). Here is my code fragment,
Can anyone points out how to improve my code so that I get the right
output. You can see the current input for just running the code. I believe
the algorithm is correct. Thanks.


void permute(char *s)

I would implement this by passing two arguments. To start call

permute( "", "abc" );

This recusively makes the following calls:

permute( "a", "bc" );
permute( "b", "ac" );
permute( "c", "ab" );

Each call permute() takes one character from the second string
and appends it to the first string.

permute( "a", "bc" ) will call:
permute( "ab", "c" )
permute( "ac", "b" )

permute( "b", "ac" ) will call:
permute( "ba", "c" )
permute( "bc", "a" )

permute( "c", "ab" ) will call:
permute( "ca", "b" )
permute( "cb", "a" )

Nick.

 

[CBFalconer]

.... snip ...

I write this function to permute a string. e.g. if the input
string is "abc", I am expecting to see the output: "abc", "acb",
"bac", "bca", "cab", "cba" there is n! output for a string of
size(n). Here is my code fragment, Can anyone points out how to
improve my code so that I get the right output. ...

.... snip code ...

I didn't attempt to check your code. Here is a version I have
used for some time:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* Public domain, by C.B. Falconer. Attribution appreciated. */

/* Things get out of hand when larger than 8 */
#define MAXWORD 12

/* ------------------ */

/* exchange 0th and ith char in wd */
void trade(char *wd, unsigned int i)
{
char c;

c = *wd;
*wd = wd;
wd = c;
} /* trade */

/* ------------------ */

/* Form all n char permutations of the characters in the
string wd of length lgh into outstring at index ix.
Output the results to stdout. */
void jumble(char *wd, unsigned int lgh,
unsigned int ix, /* output place to fill */
unsigned int n, /* max out places to fill */
char *outstring)
{
unsigned int i;

if (0 == n) {
outstring[ix] = '\0';
puts(outstring);
}
else
for (i = 0; i < lgh; i++) {
trade(wd, i); /* nop when (0 == i) */
outstring[ix] = *wd;
jumble(wd+1, lgh-1, ix+1, n-1, outstring);
trade(wd, i); /* restore the wd string */
}
} /* jumble */

/* ------------------ */

int main(int argc, char *argv[])
{
unsigned int n, lgh, min;
double max;
char outstring[MAXWORD];

if (argc < 2) {
fprintf(stderr,
"Usage: jumble <baseword> [lgh]\n"
" where the (optional) lgh specifies the\n"
" maximum length of the output words\n");
return 0;
}
lgh = strlen(argv[1]);
if (lgh >= MAXWORD) argv[1][lgh = MAXWORD-1] = '\0';

min = lgh;
if ((argc > 2) && (1 == sscanf(argv[2], "%u", &n)))
if (n && (n <= lgh)) min = n;

for (n = lgh, max = 1.0; n > (lgh - min); n--)
max = max * n;

fprintf(stderr, "string=\"%s\", max=%.0f, len=%u\n",
argv[1], max, min);

jumble(argv[1], lgh, 0, min, outstring);
return 0;
} /* main */

--
"I'm a war president. I make decisions here in the Oval Office
in foreign policy matters with war on my mind." - Bush.
"Churchill and Bush can both be considered wartime leaders, just
as Secretariat and Mr Ed were both horses." - James Rhodes.
"If I knew then what I know today, I would still have invaded
Iraq. It was the right decision" - G.W. Bush, 2004-08-02