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

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:

Will this work for repeated letters?

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.

Post a Comment