473,323 Members | 1,551 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,323 software developers and data experts.

algorithm for finding permutation of characters

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.
Jul 22 '05 #1
4 5613
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
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
Jul 22 '05 #2
On 28 Jun 2004 19:30:14 -0700 in comp.lang.c++, se********@yahoo.com (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?

Jul 22 '05 #3

"m sergei" <se********@yahoo.com> wrote in message
news:86**************************@posting.google.c 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
Jul 22 '05 #4
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" <se********@yahoo.com> wrote in message
news:86**************************@posting.google.c 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.

Jul 22 '05 #5

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
by: Mike | last post by:
Hello all, I'm looking for a free method to apply a one-way encryption to a 64-bit value in an ASP script. Does anyone have any links to existing code or at least a process that I can follow to...
4
by: jose luis fernandez diaz | last post by:
Hi, I want to write a function of four parameters. Each parameter can be of type long, double or string. For example: f(long, long, long, long); f(long, long, long, double); f(long, long,...
8
by: cayblood | last post by:
Hello, I have been interested in something kind of like the next_permutation from the STL algorithm library, except that I want it to find possible combinations of vector elements. Here is a more...
16
by: Mars | last post by:
I'm writing a program for listing all binary numbers of the same length with the same number of 1s. e.g. 0011 0101 0110 1001 1010 1100
3
by: Jack Middleton | last post by:
Hi! I'm lookin for a faster permutation algorithm for matrices. I know that it can be done with multiplying a matrix with a permutation matrix. It just seems a waste to iterate through all those...
2
by: all_my_trash | last post by:
Hello! I'm trying to write an algorithm which can fill an array with all the possible combinations of r out of n, without repetition (maximum combinations = n!/(r!(n-r)!)) However, my...
12
by: whitehatmiracle | last post by:
Dear Sir I couldnt quite figure out wat your permute function does exactly... could you please throw some light on it? void Permute(char *Perm, size_t n, size_t unchanged) { size_t outer = 0;...
4
prometheuzz
by: prometheuzz | last post by:
Hello (Java) enthusiasts, In this article I’d like to tell you a little bit about graphs and how you can search a graph using the BFS (breadth first search) algorithm. I’ll address, and...
0
by: 249740 | last post by:
Write a program that reads N phrases and determines if one phrase is a permutation of the other. For example: Phrase 1 is: “One World One Dream” Phrase 2 is: “World One One Dream”. Then the output...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.