print all permutations of string

[anurag]

hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help

[Ben Pfaff]

"Alf P. Steinbach" <al***@start.no writes:

* Noah Roberts:

>anurag wrote:

>>hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help

Knuth, Volume 4 fascicle 2.

As I recall, Knuth does not discuss or mention arithmetic coding of
permutations (using the factorial number system), so is not a complete
reference.

Is that necessary to answer the OP's question? I doubt it.
--
"doe not call up Any that you can not put downe."
--H. P. Lovecraft

[Kenneth Brody]

Lew Pitcher wrote:

>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

anurag wrote:

hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help

IIRC, this favour has been requested a number of times in recent weeks.
I wonder why the sudden interest in permuting strings using C
functions.

Perhaps from summer school assignments from all those students who
failed their C classes?

[...]
--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer .h|
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:Th***** ********@gmail. com>

[Noah Roberts]

Alf P. Steinbach wrote:

* Noah Roberts:

anurag wrote:

hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help

Knuth, Volume 4 fascicle 2.

As I recall, Knuth does not discuss or mention arithmetic coding of
permutations (using the factorial number system), so is not a complete
reference.

Yeah, I don't know what's actually in it. I have it but haven't gotten
the time to read it yet. Knuth takes me an extraordinary amount of
time to read. But it's title is "Generating all permutations and
combinations" so I figured it would be appropriate. Guy might learn
something instead of having his homework done for him.

[Simon Biber]

Alf P. Steinbach wrote:

* Noah Roberts:

>anurag wrote:

>>hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help

Knuth, Volume 4 fascicle 2.

As I recall, Knuth does not discuss or mention arithmetic coding of
permutations (using the factorial number system), so is not a complete
reference.

When you refer to arithmetic coding of permutations using the factorial
number system, are you talking about an algorithm that assigns a unique
index number to each permutation and can return any individual
permutation given its index number?

I have implemented a system like that below:

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

typedef unsigned long long ull;

/* calculate factorial of given number */
ull fact(ull a)
{
ull result = 1;
while(a) result *= a--;
return result;
}

/* generates a permutation of str and stores it in 'rs'
the permutation generated is index number 'no'
of 'np' total permutations (np == fact(strlen(str )) */
void get_perm(char *rs, const char *str, ull no, ull np)
{
size_t len = strlen(str);
ull nm = no;
ull lt;
char *p;
char temp;
strcpy(rs, str);

for(p = rs; *p; p++)
{
np = np / len;
lt = nm / np;
nm = nm % np;

temp = p[0];
p[0] = p[lt];
p[lt] = temp;

len--;
}
}

void print_all(const char *str)
{
size_t len = strlen(str);
char *rs = malloc(len + 1);
ull np = fact(len);
ull i;
if(!rs)
{
fprintf(stderr, "Error allocating memory\n");
}
else for(i = 0; i < np; i++)
{
get_perm(rs, str, i, np);
printf("%4lld: %s\n", i, rs);
}
}

int main(int argc, char **argv)
{
if(argc == 2)
{
print_all(argv[1]);
}
else
{
fprintf(stderr, "Error: require one argument for"
" string to permute\n");
}
return 0;
}

[lovecreatesbeauty]

Lew Pitcher wrote:

For the regulars: yes I know that answering a homework question is
frowned apon, and even worse is answering an algorithm question, but
this one piqued my interest. So, for my one freebie a year, I post this
code ;-)

The code gives the same amount of permutations for following two cases,
is it correct?

Permuting "abcde"
abcde
abced
....

Permuting "abcdd"
abcdd
abcdd
....

[lovecreatesbeauty]

Richard Heathfield wrote:

[comp.lang.c++ snipped - followups set to comp.lang.c]

anurag said:

hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help

Consider how you would do this by hand. For example, let's look at the
string "ABCD". We can think of the permutations of this string as being
divided into four sets (because the string is four characters long):

<snip>

If you can demonstrate your explanation with real quality code, it will
be better, and it shows you achieve what you can say.

[lovecreatesbeauty]

Ben Pfaff wrote:

"Alf P. Steinbach" <al***@start.no writes:

* Noah Roberts:

anurag wrote:
hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help
Knuth, Volume 4 fascicle 2.

As I recall, Knuth does not discuss or mention arithmetic coding of
permutations (using the factorial number system), so is not a complete
reference.

Is that necessary to answer the OP's question? I doubt it.
--
"doe not call up Any that you can not put downe."
--H. P. Lovecraft

Why? Up to now, the code given by you C experts are all wrong. Are you
all line-shooters?

[Ben Pfaff]

"lovecreatesbea uty" <lo************ ***@gmail.comwr ites:

Why? Up to now, the code given by you C experts are all wrong. Are you
all line-shooters?

Some code I wrote for generating permutations can be found in
ll_next_permuta tion and ll_prev_permuta tion at
http://cvs.savannah.gnu.org/viewcvs/...pp&view=markup
It targets linked lists, not strings.

There's a test program at
http://cvs.savannah.gnu.org/viewcvs/...=1.1&root=pspp
--
int main(void){char p[]="ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwC IxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+= strchr(p,*q++)-p;if(i>=(int)si zeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Richard Heathfield]

lovecreatesbeau ty said:

Richard Heathfield wrote:

>[comp.lang.c++ snipped - followups set to comp.lang.c]

anurag said:

hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help

Consider how you would do this by hand. For example, let's look at the
string "ABCD". We can think of the permutations of this string as being
divided into four sets (because the string is four characters long):

<snip>

If you can demonstrate your explanation with real quality code, it will
be better, and it shows you achieve what you can say.

That's great psychology, but doing his homework for him is not going to help
him one bit. If you choose to believe that I can't permute a string, that's
entirely up to you. I am not here to impress you.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Ivanna Pee]

Lew Pitcher wrote:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
anurag wrote:

hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help

IIRC, this favour has been requested a number of times in recent weeks.
I wonder why the sudden interest in permuting strings using C
functions.

In any case, to give a concrete example of what R.H. discusses
elsethread, here's an attempt I made a few weeks ago, when the question
first came up. Take it as you will.

For the regulars: yes I know that answering a homework question is
frowned apon, and even worse is answering an algorithm question, but
this one piqued my interest. So, for my one freebie a year, I post this
code ;-)

==snip==

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

void rotate(unsigned length, char *string)
{
char save;

save = *string;
while(--length)
{
*string=*(strin g+1);
++string;
}
*string = save;
}

void permute(unsigne d length, char *string, unsigned depth)
{

if (length == 0)
printf("%s\n",s tring-depth);
else
{
unsigned count;

for (count = length ; count 0; --count)
{
permute(length-1,string+1,dept h+1);
rotate(length,s tring);
}
}

}
int main(int argc, char **argv)
{
while (--argc)
{
char *source = malloc(strlen(* ++argv)+1);

if (source)
{
strcpy(source,* argv);
printf("\nPermu ting \"%s\"\n",sourc e);

permute(strlen( source),source, 0);

free(source);
}
}
return EXIT_SUCCESS;
}
==snip==

- --
Lew Pitcher
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (MingW32) - WinPT 0.11.12

iD8DBQFEv84lagV FX4UWr64RAq3YAK DBs4//FGSrc+zn7+duG2b RtCuRaQCfSnOS
mg6QbOGNExUVVsX Bp5lQYD8=
=pYBy
-----END PGP SIGNATURE-----

Now try it recursively.