2. Комбинаторные объекты

Разбор задачи 90. Реестр перестановок

Для быстрого получения `k`-й перестановки нужно уметь считать количество перестановок из заданных элементов.
Если элементы не повторяются, то количество перестановок равно `n!`.
Если в наборе есть `r` различных элемент, `i`-й элемент из них встречается `n_i` раз, то количество перестановок равно `{n!}/{n_1!*n_2!*…*n_r!}`.
Так как последние элементы при генерации перестановок всегда идут в порядке возрастания, для подсчета количество перестановок можно использовать следующую функцию:

var a:string; { строка }
    n:integer; { длина строки }
    k:int64; { номер искомой перестановки }
function kolper(i:integer);
var j,m:integer;
  r:int64;
begin
  r:=1;
  m:=0; { в какой раз встречается символ a[j] }
  for j:=i to n do
  begin
    r:=r*(j-i+1);
    if (i=j) or (a[j]=a[j-1]) then inc(m)
    else m:=1;
    r:=r div m;
  end;
  kolper:=r;
end;

Теперь для быстрого достижения `k` перестановки можно не выполнять рекурсию, если она не приводит к искомой перестановке.

procedure gen(i:integer);
var j,t:integer;
  r:int64;
begin
  if i>=n then 
  begin
    writeln(a);
    halt; { закончить выполнение программы }
  end;
  for j:=i to n do
  if (i=j) or (a[i]<>a[j]) then 
  begin 
    t:=a[i];
    a[i]:=a[j];
    a[j]:=t;
    r:=kolper(i+1);
    if k<=r then { искомая перестановка здесь }
      gen(i+1) { выполняем рекурсию }
    else { пропускаем вариант }
      k:=k-r;
  end;
  t:=a[i];
  for j:=i+1 to n do
    a[j-1]:=a[j];
  a[n]:=t;
end;

В основной программе выполняем следующие действия:

begin
  readln(a);
  readln(k);
  n:=length(a);
  gen(1);
end.