# Permutation Problem?

• 06-10-2008
chottachatri
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

• 06-10-2008
tabstop
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.)
• 06-10-2008
chottachatri
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. :)
• 06-10-2008
chottachatri
Quote:

Originally Posted by tabstop
(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? :(
• 06-10-2008
cyberfish
you can always sort the string first
• 06-10-2008
tabstop
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....)
• 06-10-2008
chottachatri
I tried working out that algorithm for abcd. These are the results that i got

abcd
abdc
acdb
acbd