program vypise_naslednika_permutace_v_lexikografickem_usporadani;
   {ze souboru nacte permutaci cisel 1...N (nevis vubec, kolik bude cisel)
   a do jineho vedle ni vypise jejiho naslednika v lexikografickem
   usporadani, jede tolikrat, kolik je ve vstupnim souboru radek
   s permutacemi. nijak nen zabraneno tomu kdyz je permutace spatne zadana!!}

const  maxn = 12;

type   tpermutace = array[1..maxn] of integer;

function cislo_permutace (n : integer; p : tpermutace) :longint;

   var  idx, fact : longint;
        i, j : integer;
   begin           { precisluj permutaci na cisla bloku }
      for i:=1 to n do
         for j:=i+1 to n do
         if (p[j]>p[i]) then p[j]:=p[j]-1;
      idx:=0;     { vypocet idx }
      fact:=1;
      for i:=n downto 1 do
         begin  { fact= (n-i)! }
            idx:=idx+(p[i]-1)*fact;
            fact:=fact * (n-i+1);
         end;
      cislo_permutace:=idx;
   end;

procedure permutace_z_cisla (idx : longint; n : integer; var p : tpermutace);
   var  i, j : integer;
        fac : longint;
   begin                              { spocti n! }
      fac:=1;
      for i:=1 to n do fac:=fac * i;  { funguje do 12!, pak pretece longint!}
      for i:=1 to n do                { vypocti cisla bloku }
         begin
            fac:=fac div (n-i+1);     { fac=(n-i)! }
            p[i]:=idx div fac + 1;    { pocet bloku pred, tj. od 0, proto +1 }
            idx:=idx mod fac;
         end;
      for i:=n downto 1 do            { precislovani cisel bloku na permutaci }
         for j:=i+1 to n do
            if (p[j]>=p[i]) then p[j]:=p[j]+1;
   end;

var
   n, k, i: integer;
   idx : longint;
   p : tpermutace;                    { cislo permutace }
   t1, t2: text;
   dobra : boolean;

begin
   assign (t1,'vstupK11.txt');
   assign (t2,'K11.txt');
   reset (t1);
   rewrite (t2);

   while not seekeof (t1) do
      begin
         i:=0;
         write (t2,'Naslednikem permutace ');
         while not seekeoln (t1) do
            begin
               read (t1,k);
               write (t2, k,' ');
               i:=i+1; n:=i;  p[i]:=k;
            end;
         write (t2,'v lexikografickem usporadani je: ');
         idx:=cislo_permutace(n, p);      { z permutace urci jeji cislo - idx }
         permutace_z_cisla(idx+1, n, p);  { z idx+1 urci jejiho naslednika }
         dobra:=true;
         for i:=1 to n do
            if p[i]>n then
               dobra:=false;          { dobra je true kdyz permutace existuje }
         if dobra=false then write (t2,'tato permutace nema naslednika')
            else
               begin
                  write (t2,' ');         { vypise permutaci }
                  for i:=1 to n do
                     write(t2,p[i],' ');
               end;
         writeln(t2);
         readln (t1);                     { aby zacal cist z noveho radku }
      end;
   close (t1);
   close (t2);
end.
