Don's Permutation

I remember the school days when I used to get fascinated by mathematics questions. After I graduated in mathematics, my love for mathematics grew stronger which unfortunately got surrounded by computer clouds.

Days passed away just like that and someday someone asked me to design an algorithm for permuting a string which reminded me of my good old school days. Somehow I managed to write the algorithm and found that it wasn’t as difficult as I had thought it to be. With full confidence I hit back to the guy with my creation (read it dirty algorithm).

Without looking into the piece of paper that I was about to hand over to him, he popped up a question, “Does you algorithm handle repeated characters present in string”? The moment he asked that question, I realized my algorithm is not only bad, it is Worst. I folded the paper and directed it into my Levi’s 501 pocket with an excuse, “No, I’ll try it at home today”, and that day never came for several years.

Once, out of habit I was troubling Google with my weird questions about Donald E. Knuth(aka Don Knuth) and got the solution of the problem.
Ok Leave the story behind. It was just to create a bad plot and to try my hands on to write something worst.

So here is the algorithm “Algorithm L” to print all possible non-repeated permutation of string of array P.


Algorithm L
Given an array
P = [a0, a1, a2,… an-2, an-1]

Start:


Label:
Loop k=n-2 to 0:
……..if k =0
……..……..“We are done”
……..if ak < ak+1
……..……..Partition P into two halves
……..……..(a0, a1, a2, …. ak) (ak+1, ak+2, … an-1)
……..……..break;
Loop ends:

Loop m = n-1 to k+1:
……..if (ak < am)
……..……..swap (ak,am)
……..……..break;
Loop ends:
reverse the second half of array i.e. (ak+1, ak+2, … an-1)
print P
go to Label:



******************************************************
I've tried to write it in as simple words as i could so it may(must) contains errors.
comments and suggestions are welcomed


Thanks
Pramod Negi