Tuesday, March 1, 2011

An algorithm to find all the permutations(anagrams) of a given string.(For eg. if abc is input algorithm should print abc, acb, bac, bca, cab and cba)


            Recursive method:
Make use of an array named selected.
For i=1 to length of the string
            select the first element which is not selected add it to the working string and increment the number of selected chars
            if number of selected chars reaches length of string, print the working string
            else, call the same function for next selection
            before continuing to the next element in the for loop unselect this element and decrease the number of elements selected and remove the element from the working string
            Non recursive method:
            Use the next perm method  using the indices.
                        Use a traversal ptr from the right.
                        Stop when a[i]<a[i+1]
                        find the smallest number x from a[i+1] to a[n] such that a[i]<x.
                        sort the remaining elements in the positions a[i+1]to a[n](including a[i]) in ascending order.
eg.
1234
next perm:1243,1324,1342,1423,1432,2134....