A
anurag
hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help
all permutations of a string.please help
V
Victor Bazarov
anurag said:
Please, for C questions do not cross-post to comp.lang.c++. Thanks!
V
F
Flash Gordon
anurag said:
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.
L
Lew Pitcher
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
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-----
Hash: SHA1
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-----
F
Francis Glassborow
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
K
Keith Thompson
Francis Glassborow said: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!
N
Noah Roberts
anurag said:
Knuth, Volume 4 fascicle 2.
A
Alf P. Steinbach
* Noah Roberts:
As I recall, Knuth does not discuss or mention arithmetic coding of
permutations (using the factorial number system), so is not a complete
reference.
As I recall, Knuth does not discuss or mention arithmetic coding of
permutations (using the factorial number system), so is not a complete
reference.
B
Ben Pfaff
Alf P. Steinbach said:
Is that necessary to answer the OP's question? I doubt it.
J
Jon Clements
Francis said:
(cross postings removed)
Strange, was a huge interest in this in comp.lang.python as well - just
the other week. Must be that bit of the course they've all gotten to!
Jon
K
Kenneth Brody
Lew said:
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:[email protected]>
N
Noah Roberts
Alf said:
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.
S
Simon Biber
Alf said:
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;
}
L
lovecreatesbeauty
Lew said:
The code gives the same amount of permutations for following two cases,
is it correct?
Permuting "abcde"
abcde
abced
....
Permuting "abcdd"
abcdd
abcdd
....
L
lovecreatesbeauty
Ben said:
Why? Up to now, the code given by you C experts are all wrong. Are you
all line-shooters?
B
Ben Pfaff
lovecreatesbeauty said:
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/pspp/src/libpspp/ll.c?rev=1.1&root=pspp&view=markup
It targets linked lists, not strings.
There's a test program at
http://cvs.savannah.gnu.org/viewcvs...t.c?content-type=text/plain&rev=1.1&root=pspp
I
Ivanna Pee
Lew said:
Now try it recursively.
M
Mark P
Noah said:
Based on their source I assume these are "legal" links to the pre-fascicles:
http://www.cs.utsa.edu/~wagner/knuth/
-Mark
- Joined
- Apr 17, 2009
- Messages
- 1
- Reaction score
- 0
Need Help
>>Lew Pitcher
Can you please explain me the algorithm for this program that you gave :captain:
I always confuse when writing recursive programs, please help me with this.
Thank you,
>>Lew Pitcher
Can you please explain me the algorithm for this program that you gave :captain:
I always confuse when writing recursive programs, please help me with this.
Thank you,