# algorithm for finding permutation of characters

Discussion in 'C++' started by m sergei, Jun 29, 2004.

1. ### m sergeiGuest

I am not asking for code but wanted help with understanding the
algorithm to permute all characters of a string.
say string is "ABCD"

I want to know the algorithm for finding all permutations of the given
string, without recursion and with recursion.

m sergei, Jun 29, 2004

2. ### Kai-Uwe BuxGuest

m sergei wrote:

> I am not asking for code but wanted help with understanding the
> algorithm to permute all characters of a string.
> say string is "ABCD"
>
> I want to know the algorithm for finding all permutations of the given
> string, without recursion and with recursion.

There is nothing as "the algorithm" to do this. There is a vast multitude
of different algorithms that have been proposed. D.E. Knuth has a chapter

http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz

Best

Kai-Uwe Bux

Kai-Uwe Bux, Jun 29, 2004

3. ### David HarmonGuest

On 28 Jun 2004 19:30:14 -0700 in comp.lang.c++, (m
sergei) wrote,
>I am not asking for code but wanted help with understanding the
>algorithm to permute all characters of a string.
>say string is "ABCD"

By "the algorithm" do you mean std::next_permutation?

David Harmon, Jun 29, 2004
4. ### John HarrisonGuest

"m sergei" <> wrote in message
news:...
> I am not asking for code but wanted help with understanding the
> algorithm to permute all characters of a string.
> say string is "ABCD"
>
> I want to know the algorithm for finding all permutations of the given
> string, without recursion and with recursion.

A non-recursive algorithm can be found by looking at the
std::next_permutation code, which will be in the header file <algorithm>
that comes with your compiler (or possibly in another header file that is
included by <algorithm>, search around you'll find it).

john

John Harrison, Jun 29, 2004
5. ### Philip ParkerGuest

one way of doing it with recursion. should do all chars in a,b,c,d,e as so:
a-b, a-c, a-d, a-e
b-c, b-d, b-e
c-d, c-e
d-e

for (int i=0; i<numofchars; i++) {
for (int j=(i+1);j<numofchars;j++) {
// do something with the char at i, and the char at j
}
}

"m sergei" <> wrote in message
news:...
> I am not asking for code but wanted help with understanding the
> algorithm to permute all characters of a string.
> say string is "ABCD"
>
> I want to know the algorithm for finding all permutations of the given
> string, without recursion and with recursion.

Philip Parker, Jun 29, 2004