What parameters are passed to the generator:
- x - word number;
- N is the size of the alphabet;
- L is the length of the output word.
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:
- 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
- ...
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;
}
Aucun commentaire:
Enregistrer un commentaire