|
|
|
|
|
|
| Author |
Message |
anurag
*nix forums beginner
Joined: 20 Jul 2006
Posts: 1
|
 Posted: Thu Jul 20, 2006 5:57 pm Post subject:
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 |
|
| Back to top |
|
 |
Victor Bazarov
*nix forums Guru
Joined: 07 Apr 2005
Posts: 3949
|
| Posted: Thu Jul 20, 2006 5:59 pm Post subject:
Re: print all permutations of string
|
|
|
anurag wrote:
| Quote: | 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 |
|
| Back to top |
|
|
neutron*star
*nix forums Guru
Joined: 21 Feb 2005
Posts: 2039
|
| Posted: Thu Jul 20, 2006 6:13 pm Post subject:
Re: print all permutations of string
|
|
|
[comp.lang.c++ snipped - followups set to comp.lang.c]
anurag said:
| Quote: | 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) |
|
| Back to top |
|
|
Flash Gordon
*nix forums Guru
Joined: 28 Feb 2005
Posts: 1258
|
| Posted: Thu Jul 20, 2006 6:22 pm Post subject:
Re: print all permutations of string
|
|
|
anurag wrote:
| Quote: | 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 |
|
| Back to top |
|
|
Lew Pitcher
*nix forums Guru
Joined: 21 Feb 2005
Posts: 675
|
| Posted: Thu Jul 20, 2006 6:41 pm Post subject:
Re: print all permutations of string
|
|
|
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
anurag wrote:
| Quote: | 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----- |
|
| Back to top |
|
|
usenet@zevv.nl
*nix forums Guru Wannabe
Joined: 29 Nov 2005
Posts: 141
|
| Posted: Thu Jul 20, 2006 7:23 pm Post subject:
Re: print all permutations of string
|
|
|
In comp.lang.c Richard Heathfield <invalid@invalid.invalid> wrote:
| Quote: | [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... ]
| Quote: | ... 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 |
|
| Back to top |
|
|
Francis Glassborow
*nix forums addict
Joined: 09 Apr 2005
Posts: 67
|
| Posted: Thu Jul 20, 2006 8:52 pm Post subject:
Re: print all permutations of string
|
|
|
In article <1153418276.122549.15570@m79g2000cwm.googlegroups.com>,
anurag <anurag1408@gmail.com> writes
| Quote: | 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 |
|
| Back to top |
|
|
Keith Thompson
*nix forums Guru
Joined: 28 Feb 2005
Posts: 5173
|
| Posted: Thu Jul 20, 2006 9:46 pm Post subject:
Re: print all permutations of string
|
|
|
Francis Glassborow <francis@robinton.demon.co.uk> writes:
| Quote: | In article <1153418276.122549.15570@m79g2000cwm.googlegroups.com>,
anurag <anurag1408@gmail.com> writes
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) kst-u@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. |
|
| Back to top |
|
|
Alf P. Steinbach
*nix forums Guru
Joined: 09 Mar 2005
Posts: 1855
|
| Posted: Thu Jul 20, 2006 10:28 pm Post subject:
Re: print all permutations of string
|
|
|
* Noah Roberts:
| Quote: | 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? |
|
| Back to top |
|
|
Ben Pfaff
*nix forums Guru
Joined: 08 Apr 2005
Posts: 661
|
| Posted: Thu Jul 20, 2006 10:31 pm Post subject:
Re: print all permutations of string
|
|
|
"Alf P. Steinbach" <alfps@start.no> writes:
| Quote: | * 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 |
|
| Back to top |
|
|
Kenneth Brody
*nix forums Guru
Joined: 20 Apr 2005
Posts: 401
|
| Posted: Fri Jul 21, 2006 12:09 am Post subject:
Re: print all permutations of string
|
|
|
Lew Pitcher wrote:
| Quote: |
-----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:ThisIsASpamTrap@gmail.com> |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Mon Dec 01, 2008 7:33 pm | All times are GMT
|
|
Mortgage Calculator | Loans | Refinance | Credit Cards | Discount Magazines
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
|
|
Other DeniX Solutions sites:
Unix/Linux blog |
electronics forum |
medicine forum |
science forum |
|
|
Privacy Policy
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Programming
»
C
