program perm;

{$MODE OBJFPC}{$H+}

type
  TNPermutationVector = array of Byte;
  TNPermutationElements = set of Byte;

  PNPermutation = ^TNPermutation;
  TNPermutation = record
    // Anzahl Spieler (Elemente des Permutationsvektors)
    nr: Integer;
    // Info für aktuelle Teilpermutation
    perm_index: Integer;
    // Aktueller Permutationsvektor
    cur_perm: TNPermutationVector;
  end;
  
function init_permutation( ANumber: Byte ): PNPermutation;
var i: Integer;
begin
  Result := New(PNPermutation);
  Result^.nr := ANumber;
  
  // nächster Schritt permutiert ((nr-perm_index)..nr) -> die letzten 2 Stellen
  Result^.perm_index := 1;

  // Es gibt keine Permutation mit 0 elementen -- exit
  if ANumber <= 0 then Exit;

  // Erzeuge InitalVektor - erste Permutation
  SetLength(Result^.cur_perm, ANumber);
  for i := 1 to ANumber do
    Result^.cur_perm[i-1] := i;
end;

function next_permutation( pnperm: PNPermutation ): Boolean;
var fix_elements: TNPermutationElements;
    i: Integer;
    tmpb, tmpi: Integer;
begin
  Result := true;
  
  // alle möglichen Permutationen abgearbeitet -> abbruch
  if pnperm^.perm_index >= pnperm^.nr then
    Exit(false);

  fix_elements := [];

  if pnperm^.perm_index > 1 then
    begin
      // bestimme alle nicht freien Zahlen bis perm_index
      for i := 0 to pnperm^.nr-(pnperm^.perm_index+2) do
        Include(fix_elements,pnperm^.cur_perm[i]);
      // bestimmte die nächst größere, freie Zahl für perm_index
      tmpb := pnperm^.cur_perm[pnperm^.nr-(pnperm^.perm_index+1)];
      for i := tmpb+1 to pnperm^.nr do
        if not (i in fix_elements) then
          begin
            tmpb := i;
            break;
          end;
      // check - nächste zahl wurde ausgewählt
      ASSERT(tmpb <> pnperm^.cur_perm[pnperm^.nr-(pnperm^.perm_index+1)]);
      // neue Zahl wird festgelegt
      Include(fix_elements,tmpb);
      pnperm^.cur_perm[pnperm^.nr-(pnperm^.perm_index+1)] := tmpb;
      
      // erzeuge neuen initialvektor mit den restlichen freien Zahlen
      tmpi := pnperm^.nr-pnperm^.perm_index;
      for i := 1 to pnperm^.nr do
        begin
          if not (i in fix_elements) then
            begin
              pnperm^.cur_perm[tmpi] := i;
              Inc(tmpi,1);
            end;
        end;
        
      // nach diesem schritt ist die nächste permutation jene, die aus dem wechsel
      // der letzten 2 elemente erzeugt wird -> perm_index = 1
      pnperm^.perm_index := 1;
    end
  else
    begin
      // einfachster Fall, permutation der letzten 2 Stellen -> tauschen
      tmpb := pnperm^.cur_perm[pnperm^.nr-1];
      pnperm^.cur_perm[pnperm^.nr-1] := pnperm^.cur_perm[pnperm^.nr-2];
      pnperm^.cur_perm[pnperm^.nr-2] := tmpb;
      
      // das komplexe - bestimmung des nächsten perm_index
      // -- backtracking algorithmus:
      //  1. die letzten 2 elemente wurden gewechselt  -> sie sind frei
      //  2. nächster perm_index is der höchste index, für die eine freie
      //     Zahl gewählt werden kann, die größer ist als die aktuelle in
      //     den Elementen der Teilpermutation (nr-perm_index)..nr
            
      // Markiere alle Elemente als Fest
      for i := 1 to pnperm^.nr do
        Include(fix_elements,i);
      
      // die letzten elemente der aktuellen Permutation sind frei (1.)
      Exclude(fix_elements,pnperm^.cur_perm[pnperm^.nr-1]);  
      Exclude(fix_elements,pnperm^.cur_perm[pnperm^.nr-2]);
      
      // bestimme den nächsten perm_index, ist perm_index >= nr, dann wurden
      // alle permutationen der nr elemente aufgezählt -> abbruchbedingung
      pnperm^.perm_index := 2;
      while pnperm^.perm_index < pnperm^.nr do
        begin
          // prüfe ob es eine nächstgrößere zahl in den freien elementen gibt
          tmpb := pnperm^.cur_perm[pnperm^.nr-(pnperm^.perm_index+1)];
          tmpi := tmpb;
          for i := tmpb+1 to pnperm^.nr do
            if not (i in fix_elements) then
              begin
                tmpb := i;
                break;
              end;          
          if tmpi >= tmpb then
            begin
              // keine solche Zahl gefunden -> diese teilpermutation ist 
              // abgearbeitet, versuche die nächste teilpermutation - tmpb
              // ist damit ebenfalls frei
              Exclude(fix_elements,tmpb);
              Inc(pnperm^.perm_index,1);
            end
          else
            begin
              // Zahl/Perm_Index bestimmt - abbruch
              break;
            end;
        end;
    end;
end;

procedure fini_permutation( pnperm: PNPermutation );
begin
  SetLength(pnperm^.cur_perm,0);
  Dispose(pnperm);
end;

procedure print_permutation( pnperm: PNPermutation );
var i: Integer;
begin
  for i := 0 to pnperm^.nr-1 do
    Write( 'P[',i+1,']=',pnperm^.cur_perm[i],',' );
  WriteLn(' PermIndex=',pnperm^.perm_index);
end;

var
  TestPermuter: PNPermutation;

begin
  TestPermuter := init_permutation(4);
  repeat
    print_permutation(TestPermuter);
  until not next_permutation(TestPermuter);
  fini_permutation(TestPermuter);
end.