What parameters are passed to the generator:
It is necessary to implement a non-recursive algorithm that will return a word based on the three parameters passed.
Alphabet - Latin letters in alphabetical order, caps.
For N = 5, L = 3 we construct a correspondence of x to words:
My implementation of the algorithm works for L = 1; 2. But errors appear on L = 3. The algorithm is based on shifts when accessing the alphabet. The h array stores the indices of the letters in the new dictionary (from which the characters that have already entered the word are excluded). Array A stores casts of indices h into the original dictionary (adds indents for each character removed from the alphabet to the left). Thus, in the end, array A stores Permutations without repetitions.
private static String getS (int x, int N, int L) {
String s = "ABCDEFGHJKLMNOPQ";
String out = "";
int [] h = new int [N];
int [] A = new int [N];
for (int i = 0; i <L; i ++) {
h [i] = (x / (factory (N - 1 - i) / factory (N - L)))% (N-i);
int sum = h [i];
for (int j = 0; j <i; j ++)
sum + = ((h [i]> = h [j])? 1: 0);
A [i] = sum;
out + = s.charAt (A [i]);
}
return out;
}
To generate a random word of length L: keep the alphabet in an array of size N, and get a random word of length L by swapping the i'th element for a random element in i to N-1 for i in [0, L-1].
To generate the x'th word of length L in alphabetical order: Note that for a word of size L made up of distinct letters from an alphabet of size N, there are (N-1)! / (N-L)! words starting with any given letter.
E.g., N=5, L=3, alphabet = ABCDE. The number of words starting with A (or any letter) is 4! / 2! = 12. These are all the ordered N-L-length subsets of the available N-1 letters.
So the first letter of word(x, N, L) is the x / ((N-1)! / (N-L)!) letter of the alphabet (zero-indexed).
You can then build your word recursively.
E.g., word(15, 5, 3, ABCDE): The first letter is 15 / (4! / 2!) = 15 / 12) = 1, so B.
We get the second letter recursively: word((15 % (4! / 2!), 4, 2, ACDE) = word(3, 4, 2, ACDE). Since 3 / (3! / 2!) = 3 / 3 = 1, the second letter is C.
Third letter: word(3%3, 3, 1, ADE) = word(0, 3, 1, ADE) = A.
0. ABC
1. ABD
2. ABE
3. ACB
4. ACD
5. ACE
6. ADB
7. ADC
8. ADE
9. AEB
10. AEC
11. AED
12. BAC
13. BAD
14. BAE
15. BCA