algorithm for finding permutation of characters

M

m sergei

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

Kai-Uwe Bux

m said:
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
on this, which you can download:

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

It is about 60 pages.


Best

Kai-Uwe Bux
 
D

David Harmon

On 28 Jun 2004 19:30:14 -0700 in comp.lang.c++, (e-mail address 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?
 
J

John Harrison

m sergei said:
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
 
P

Philip Parker

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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top