Thursday, August 28, 2008

Nth permutation without swapping; without recursion

Colleagues say I have good pattern recognition skills. It's perhaps this skill that gave me a unique solution to one of our assignment problems when I was doing my rigorous PGDST course at C-DAC.

You'd get many programs for finding the N'th lexicographic (alphabetical order) permutation of a string. They're done with recursion and swapping.
I present you a completely unique algorithm which I've devised myself. It makes use of no recursion or swapping. Besides, the algorithm is WAY shorter than the others.

Consider you have a string with 'e' elements. You're asked to find the N'th lexicographic permutation.
The sequence for three elements would be:
abc, acb, bac, bca, cab, cba

But my algorithm won't even have to generate this list. It directly reaches the Nth permutation. How? Read on...



The Algorithm:
 
1. e=number of elements in string. [Store them in an array as 'abc', where a is in the zero'th position of the array]
2. n=n'th permutation of the string.
3. division=(e!)/e [This divides the list into equal sections](where e! is 'e factorial'. If e=3, e!=3*2*1)
4. Calculate pos=ceil(n/division) to find where the n'th string would be in the list.
5. Find the pos-1 element in the array.
6. Concatenate the element found from step 5, in the final output string.
7. e=e-1 [decrease the number of elements]
8. Remove the pos-1 element from the array and reinitialize the array with only the leftover characters.
9. oldDivision=division [store temporarily]
10. n=n-(oldDivision*(pos-1))
11. Goto step 3 if you haven't iterated 'length of the original string' times.
12. Print the output string.



The code:

package nthpermutation;

public class NthPermutation {

 public static void main(String[] args) {

     int NthPermutationToConsider = 1;//change this number to the value of N you want

     String sampleString = "abcd";
     int numberOfLettersForPermutation = sampleString.length();

     String[] oneLetter = new String[numberOfLettersForPermutation];
     String outputString = "";//string to be outputString
     for (int i = 0; i < numberOfLettersForPermutation; i++) {
         oneLetter[i] = sampleString.substring(i, i + 1);
     }

     int elements;
     double pos;
     float oldDivision;
     float division;
     elements = numberOfLettersForPermutation;
     oldDivision = 0;

     for (int i = 0; i < numberOfLettersForPermutation; i++) {
         division = fac(elements) / elements;
         float temp = NthPermutationToConsider / division;
         pos = Math.ceil(temp);
         outputString = outputString + oneLetter[(int) pos - 1];
         oneLetter[(int) pos - 1] = "999";
         elements--;
         String[] t = new String[elements];
         int counter = 0;
         for (int j = 0; j < oneLetter.length; j++) {
             if (!oneLetter[j].equals("999")) {
             t[counter++] = oneLetter[j];
         }
     }
     oneLetter = t;
     oldDivision = division;
     NthPermutationToConsider = NthPermutationToConsider - ((int) oldDivision * ((int) pos - 1));
 }
     System.out.println(outputString);
 }//main

 private static int fac(int n) {
     int j = 1;
     for (int i = 1; i <= n; i++) {
         j = j * i;
     }
     return j;
 }

}//class

2 comments:

Anonymous said...

Will this work for repeated letters?

Navin Ipe said...

Dear Anonymous, before I answer your question, perhaps I could mention that I would have loved it if you tried it yourself first and then let me know. Please do. Also, do mention any other conditions you are trying it under.