Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > print all permutations of string

Reply
Thread Tools

print all permutations of string

 
 
Kenneth Brody
Guest
Posts: n/a
 
      07-21-2006
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: <(E-Mail Removed)>

 
Reply With Quote
 
 
 
 
Noah Roberts
Guest
Posts: n/a
 
      07-21-2006

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.

 
Reply With Quote
 
 
 
 
Simon Biber
Guest
Posts: n/a
 
      07-21-2006
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;
}
 
Reply With Quote
 
lovecreatesbeauty
Guest
Posts: n/a
 
      07-25-2006

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

 
Reply With Quote
 
lovecreatesbeauty
Guest
Posts: n/a
 
      07-25-2006
Ben Pfaff wrote:
> "Alf P. Steinbach" <(E-Mail Removed)> 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?

 
Reply With Quote
 
Ben Pfaff
Guest
Posts: n/a
 
      07-25-2006
"lovecreatesbeauty" <(E-Mail Removed)> writes:

> 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;}
 
Reply With Quote
 
Ivanna Pee
Guest
Posts: n/a
 
      07-25-2006

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.

 
Reply With Quote
 
Mark P
Guest
Posts: n/a
 
      07-25-2006
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
 
Reply With Quote
 
karteek007 karteek007 is offline
Junior Member
Join Date: Apr 2009
Posts: 1
 
      04-17-2009
>>Lew Pitcher

Can you please explain me the algorithm for this program that you gave

I always confuse when writing recursive programs, please help me with this.

Thank you,
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Best way to print all possible permutations of a string sanket C++ 3 11-30-2011 04:55 AM
How to print permutations? Shraddha C++ 5 05-26-2007 02:56 PM
print all permutations of string anurag C Programming 20 07-25-2006 06:47 PM
How to generate all permutations of a string? Girish Sahani Python 11 06-26-2006 06:16 PM
Re: How to generate all permutations of a string? Maric Michaud Python 0 06-22-2006 10:24 AM



Advertisments