473,287 Members | 1,555 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,287 software developers and data experts.

print all permutations of string

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

Jul 20 '06 #1
20 41239
anurag wrote:
hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help
Please, for C questions do not cross-post to comp.lang.c++. Thanks!

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Jul 20 '06 #2
[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):

1) All the strings starting with A and continuing with some permutation of
BCD
2) All the strings starting with B and continuing with some permutation of
CDA
3) All the strings starting with C and continuing with some permutation of
DAB
4) All the strings starting with D and continuing with some permutation of
ABC

As you might imagine, you can get at these sets simply by moving the string
around a little.

Let's look at just one of these sets (because the others are dealt with in
the same way, obviously): strings starting with A and continuing with some
permutation of BCD.

We are now faced with the problem of finding all the strings containing BCD
(which we can simply append to A to get the full permutation).

We can think of the permutations of this string as being divided into three
sets (because the string is three characters long):

1) All the strings starting with B and continuing with some permutation of
CD
2) All the strings starting with C and continuing with some permutation of
DB
3) All the strings starting with D and continuing with some permutation of
BC

As you might imagine, you can get at these sets simply by moving the string
around a little.

Let's look at just one of these sets (because the others are dealt with in
the same way, obviously): strings starting with (A and then) B and
continuing with some permutation of CD.

We are now faced with the problem of finding all the strings containing CD
(which we can simply append to AB to get the full permutation).

We can think of the permutations of this string as being divided into two
sets (because the string is two characters long):

1) All the strings starting with C and continuing with some permutation of D
2) All the strings starting with D and continuing with some permutation of C

As you might imagine, you can get at these sets simply by moving the string
around a little.

Let's look at just one of these sets (because the others are dealt with in
the same way, obviously): strings starting with (A and then B and then) C,
and continuing with some permutation of D.

We are now faced with the problem of finding all the strings containing D
(which we can simply append to ABC to get the full permutation).

We can think of the permutations of this string as being divided into one
set (because the string is one character long):

1) All the string starting with D - which is obvious, of course.

The canonical way to do this is via recursion, passing in the string,
together with the number of items yet to be permuted. If that number is 0,
simply display the string. Otherwise, loop around the leftmost
not-yet-handled character and, within the loop, recurse with n-1.

Now take a crack at it yourself, and let us know how you get on.

--
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)
Jul 20 '06 #3
-----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=*(string+1);
++string;
}
*string = save;
}

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

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

for (count = length ; count 0; --count)
{
permute(length-1,string+1,depth+1);
rotate(length,string);
}
}

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

if (source)
{
strcpy(source,*argv);
printf("\nPermuting \"%s\"\n",source);

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

iD8DBQFEv84lagVFX4UWr64RAq3YAKDBs4//FGSrc+zn7+duG2bRtCuRaQCfSnOS
mg6QbOGNExUVVsXBp5lQYD8=
=pYBy
-----END PGP SIGNATURE-----

Jul 20 '06 #4
anurag wrote:
hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help
Yes. First learn that C++ and C are different languages, so posting to
comp.lang.c++ is entirely inappropriate if you want a C solution.

Having excluded comp.lang.c++ you should first try to write your
algorithm. comp.lang.c does not generally help with algorithms,
comp.programming and alt.comp.lang.c-c++ might, check the groups out to
see. comp.lang.c discusses the C language and helps people with C problems.

Then, post specific questions rather than just asking someone to help
you writing it. A lot of us could write the function in less time that
it would take to explain it to you, but this would not help you to learn.

If you don't know where to start, then I suggest you start off by trying
to write all the permutations of a short string by hand rather than
trying to write a program to do it. Then you can analyse how you did it
and try to formalise that in to an algorithm.

I've excluded comp.lang.c++ from the follow-ups. When you have decided
whether you have a problem with the C language or with writing the
algorithm please cut the posting down to only the most appropriate group.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc
Jul 20 '06 #5
Ico
In comp.lang.c Richard Heathfield <in*****@invalid.invalidwrote:
[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 ...
[ ...snipped yet another lengthy explanation... ]
... string. Otherwise, loop around the leftmost
not-yet-handled character and, within the loop, recurse with n-1.

Now take a crack at it yourself, and let us know how you get on.
I admire your patience, I really do...

--
:wq
^X^Cy^K^X^C^C^C^C
Jul 20 '06 #6
In article <11*********************@m79g2000cwm.googlegroups. com>,
anurag <an********@gmail.comwrites
>hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help
That looks like homework. In addition it is under specified. Are the
characters in the string all unique or are repeats allowed? If they are
all unique it is very easy :)

--
Francis Glassborow ACCU
Author of 'You Can Do It!' and "You Can Program in C++"
see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
Jul 20 '06 #7
Francis Glassborow <fr*****@robinton.demon.co.ukwrites:
In article <11*********************@m79g2000cwm.googlegroups. com>,
anurag <an********@gmail.comwrites
>>hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help

That looks like homework. In addition it is under specified. Are the
characters in the string all unique or are repeats allowed? If they
are all unique it is very easy :)
Not as easy as if they're all the same!

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Jul 20 '06 #8

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.

Jul 20 '06 #9
* 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.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Jul 20 '06 #10
"Alf P. Steinbach" <al***@start.nowrites:
* 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
Jul 20 '06 #11
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>

Jul 21 '06 #12

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.

Jul 21 '06 #13
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;
}
Jul 21 '06 #14

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
....

Jul 25 '06 #15
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.

Jul 25 '06 #16
Ben Pfaff wrote:
"Alf P. Steinbach" <al***@start.nowrites:
* 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?

Jul 25 '06 #17
"lovecreatesbeauty" <lo***************@gmail.comwrites:
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_permutation and ll_prev_permutation 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[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
Jul 25 '06 #18
lovecreatesbeauty 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)
Jul 25 '06 #19

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=*(string+1);
++string;
}
*string = save;
}

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

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

for (count = length ; count 0; --count)
{
permute(length-1,string+1,depth+1);
rotate(length,string);
}
}

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

if (source)
{
strcpy(source,*argv);
printf("\nPermuting \"%s\"\n",source);

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

iD8DBQFEv84lagVFX4UWr64RAq3YAKDBs4//FGSrc+zn7+duG2bRtCuRaQCfSnOS
mg6QbOGNExUVVsXBp5lQYD8=
=pYBy
-----END PGP SIGNATURE-----
Now try it recursively.

Jul 25 '06 #20
Noah Roberts wrote:
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.
Based on their source I assume these are "legal" links to the pre-fascicles:

http://www.cs.utsa.edu/~wagner/knuth/

-Mark
Jul 25 '06 #21

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

11
by: Girish Sahani | last post by:
Hi guys, I want to generate all permutations of a string. I've managed to generate all cyclic permutations. Please help :) def permute(string): l= l.append(string) string1 = '' for i in...
17
by: anurag | last post by:
hey can anyone help me in writing a code in c (function) that prints all permutations of a string.please help
1
by: JosAH | last post by:
Greetings, last week we talked a bit about generating permutations and I told you that this week will be about combinations. Not true; there's a bit more to tell about permutations and that's...
5
by: Shraddha | last post by:
If we have three variables a,b,c...which are char variables....then hoe to print there all permutations? for example....abc, bac, cab.......all of them....
5
by: Shraddha | last post by:
Suppose we are having 3 variables...a,b,c And we want to print the permutations of these variables...Such as...abc,acb,bca...all 6 of them... But we are not supposed to do it mannually... I...
2
by: Assimalyst | last post by:
Hi I have a Dictionary<string, List<string>>, which i have successfully filled. My problem is I need to create a filter expression using all possible permutations of its contents. i.e. the...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.