Velocity Reviews > C++ > algorithm for finding permutation of characters

algorithm for finding permutation of characters

m sergei
Guest
Posts: n/a

 06-29-2004
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.

Kai-Uwe Bux
Guest
Posts: n/a

 06-29-2004
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

David Harmon
Guest
Posts: n/a

 06-29-2004
On 28 Jun 2004 19:30:14 -0700 in comp.lang.c++, http://www.velocityreviews.com/forums/(E-Mail Removed) (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?

John Harrison
Guest
Posts: n/a

 06-29-2004

"m sergei" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) om...
> 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

Philip Parker
Guest
Posts: n/a

 06-29-2004
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" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) om...
> 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.