Генератор случайных слов без повторяющихся букв без поиска

Question

Какие параметры передаются генератору:

x - номер слова;
N - размер алфавита;
L - длина выходного слова.

Необходимо реализовать нерекурсивный алгоритм, который по переданным трём параметрам будет возвращать слово.

Алфавит - латинские буквы в алфавитном порядке, капсом.

Для N=5, L=3 построим соответствие x словам:

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
...

Моя реализация алгоритма работает на L=1; 2. Но на L=3 появляются ошибки. Сам алгоритм построен на сдвигах при обращении к алфавиту. Массив h хранит индексы букв в новом словаре (из которого исключены символы, которые уже попали в слово). Массив A хранит приведения индексов h в исходный словарь (добавляет отступы за каждый удалённый из алфавита символ слева). Таким образом, в конечном итоге, массив A хранит размещения без повторений.

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;
}

Answer 1

Существует F=A(N, L) = N!/(N-L)! нужных размещений.

Так что можно сгенерировать случайное число в диапазоне 0..F-1 и построить размещение, соответствующее этому номеру.

А чтобы получить размещение по номеру (в лексикографическом порядке), можно использовать следующее - первый элемент множества стоит на первом месте в A(n-1,l-1) размещений (в примере из вопроса это 12 штук, начинающихся с A). Затем исключаем использованный элемент из списка, и аналогично находим элемент на второй позиции и т.д.

Вот пример на Delphi из этого ответа (div - целочисленное деление, mod, остаток от деления, %)

Для аргументов 5, 3, 15 (номер 15) получается размещение 1,2,0, соответствующее BCA

function ArrangementByRank(n, k, rank: Integer): string;

    function NumArrNK(n, k: Integer): Int64;
    var
      i: Integer;
    begin
      Result := 1;
      for i := 0 to k - 1 do
        Result := Result * (n - i);
    end;

  var
    Dig: array of Byte;
    i, j, id, ank: Integer;
  begin
    Result := '';
    SetLength(Dig, n);
    for i := 0 to n - 1 do
       Dig[i] := i;  //initial digit list

    for i := 1 to k do begin
      ank := NumArrNK(n - i, k - i);  //might be optimized
      id := rank div ank;
      rank := rank mod ank;   //prepare for the next round
      Result := Result + IntToStr(Dig[id]);
      for j := id to n - i - 1 do
        Dig[j] := Dig[j + 1];  //squeeze digit list
    end;
  end;

Перевод на Java: (тест на IdeOne)

public static int NumArrNK(int n, int k) {
    int out = 1;

    for (int i = 0; i <= k - 1; i++)
        out *= n - i;

    return out;
}

public static String ArrByR(int n, int k, int x){
    String s = "ABCDEFGHJKLMNOPQ";
    int[] Dig = new int[n];

    int id, ank;

    String out = "";

    for (int i = 0; i < n; i++)
        Dig[i] = i;

    for (int i = 1; i <= k; i++) {

        ank = NumArrNK(n - i, k - i);  //might be optimized
        id = x / ank;
        x = x % ank;   //prepare for the next round
        out = out + s.charAt(Dig[id]);

        for (int j = id; j < n - i; j++)
            Dig[j] = Dig[j + 1];

    }

    return out;
}

БЛОГ НА HUSL

Генератор случайных слов без повторяющихся букв без поиска

Ответы (1 шт):