Thread: 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!!

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.)

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?

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....)

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