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
