Перестановки из n элементов с повторениями – это перестановки из n элементов, в каждую из которых входят n1 элементов 1-го типа, n2 элементов 2-го типа…, nm элементов m-го типа, где n1+n2+n +…+nm=n.
Pn(n1, n2, … nm) = n!/n1*n2*…*nm
Если m=3, b=’xyz’, kp=[2, 3, 2], ( в массиве kp записано сколько раз повторятся i-той букве как написано в примере) то перестановки с повторениями будут такими:
01122233 => xxyyyzz
01122323 => xxyyzyz
01122332 => xxyyzzy
01123223 => xxyzyyz
01123232 => xxyzyzy
…
03322211 => zzyyyxx
Словесный алгоритм тот же, что и в обычных перестановках.
P.S. Спасибо Барбаре за теорию
Код:
var b:string; p,kp:array [0..255] of integer; n,i,j,d,k,l,s:longint;
begin
readln(b);
n:=length(b);
for i:=1 to n do read(kp[i]);
p[0]:=0;
for i:=1 to n do
for j:=1 to kp[i] do
begin
l:=l+1;
p[l]:=i;
end;
n:=l;
while p[0]=0 do
Begin
for i:=1 to n do write(b[p[i]]);
writeln;
s:=s+1;
j:=n;
while p[j-1]>=p[j] do j:=j-1;
k:=n;
while p[j-1]>=p[k] do k:=k-1;
d:=p[k];
p[k]:=p[j-1];
p[j-1]:=d;
for i:=j to (n+j-1)div 2 do
begin
d:=p[i];
p[i]:=p[n-i+j];
p[n-i+j]:=d;
end;
end;
writeln(s);
end.
