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!!
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.)
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. :)
Please tabstop explain me what do you mean by swap the next one? :(
Originally Posted by tabstop
you can always sort the string first
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....)
I tried working out that algorithm for abcd. These are the results that i got
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?
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.
Ok thanks! :) now let me further try out on paper then i will try to code. Thanks tabstop again:)