dimanche 7 mars 2021

Generator of random words without repeating letters without searching

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