[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)