Permutation Problem?

This is a discussion on Permutation Problem? within the C++ Programming forums, part of the General Programming Boards category; Hello, please tell me the algorithm on how to permute a string? like for abcd it should be abcd,abdc.....and ya ...

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    225

    Permutation Problem?

    Hello,
    please tell me the algorithm on how to permute a string? like for abcd it should be abcd,abdc.....and ya i have solved this problem recursively. I want to do it in a non-recursive manner. First tell me it possible to generate such variable number of loops for permutation? Secondly i don't want to use any stack. The solution should be entirely based on pure loops only! Is it possible to do so!If yes then kindly give me the algorithm else give me hints that can be of any use to me

    Thanks in advance!!

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    The algorithm's fairly well known, I should think; I wouldn't be at all surprised if you found it in your discrete math/algorithms textbook. But anyway, the idea is, roughly, to take the element currently at the end, swap it with the first element working backwards "less" than it, then reverse the bit to the right. So for instance, with abdc, you would take the c and swap it with the b (the nearest element that's less) to get acdb, and then reverse the part to the right to get acbd. (If the last element can't swap, like in bcda, then you try to swap the next one.)

  3. #3
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    Nice algorithm tabstop!
    But still my doubt is that if we give string as abcd then it's fine! but what if i give the input string as dcba?? Will this algorithm work for this string??Also if i give string as cbda then will the algorithm generate all correct 24 permutations?

    Thanks for the algorithm anyways! i didn't knew this.
    Last edited by chottachatri; 06-10-2008 at 09:05 PM.

  4. #4
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    Quote Originally Posted by tabstop View Post
    (If the last element can't swap, like in bcda, then you try to swap the next one.)
    Please tabstop explain me what do you mean by swap the next one?

  5. #5
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    you can always sort the string first

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Since the algorithm is designed to give things in slphabetical order, you should sort first.

    In terms of "swap the next one", if you can't swap letter #n, try to swap #n-1. (And if that doesn't work, try #n-2....)

  7. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    I tried working out that algorithm for abcd. These are the results that i got


    abcd
    abdc
    acdb
    acbd
    adbc
    adcb

    bdca
    bdac


    Till here i have worked out. Please let me know if i am doing the problem correctly and where do i proceed from here? which letters should i swap?
    Last edited by chottachatri; 06-10-2008 at 09:28 PM.

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    The first six are fine. You forgot to do the reverse bit for the seventh, so the first b should be bacd. When you do get to bcda, you can't swap the a, so you go for the d -- the d swaps with the c (the nearest lesser letter) to get bdca, then you reverse to get bdac.

  9. #9
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    Ok thanks! now let me further try out on paper then i will try to code. Thanks tabstop again

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 10:22 AM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  5. Problem creating a recursive string permutation function
    By indigo0086 in forum C++ Programming
    Replies: 4
    Last Post: 10-10-2006, 10:09 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21