algorithm for finding permutation of characters

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

  1. m sergei

    m sergei Guest

    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
    #1
    1. Advertising

  2. m sergei

    Kai-Uwe Bux Guest

    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
    Kai-Uwe Bux, Jun 29, 2004
    #2
    1. Advertising

  3. m sergei

    David Harmon Guest

    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
    #3
  4. "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
    #4
  5. 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
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Roger B.
    Replies:
    13
    Views:
    603
    D.F.S.
    Sep 26, 2003
  2. Sriram Rajagopalan

    String Permutation function in C

    Sriram Rajagopalan, Oct 29, 2003, in forum: C Programming
    Replies:
    7
    Views:
    13,163
  3. Talin

    Permutation Generator

    Talin, Aug 12, 2005, in forum: Python
    Replies:
    10
    Views:
    15,023
    Gerard Flanagan
    Aug 15, 2005
  4. Jack Middleton

    Faster matrix permutation algorithm?

    Jack Middleton, Aug 13, 2005, in forum: C Programming
    Replies:
    3
    Views:
    750
    russell kym horsell
    Aug 14, 2005
  5. Replies:
    12
    Views:
    642
Loading...

Share This Page