Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

print all permutations of string

 
 
Ben Pfaff
Guest
Posts: n/a
 
      07-20-2006
"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
 
Reply With Quote
 
 
 
 
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
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.

 
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
 
Richard Heathfield
Guest
Posts: n/a
 
      07-25-2006
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)
 
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
 
 
 
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
print all permutations of string anurag C++ 18 04-17-2009 02:48 PM
How to print permutations? Shraddha C++ 5 05-26-2007 02:56 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