����������: ������������� � �������.

H��������� ��� ������������ ����� 1..N.

����� ����� ������������ ����� N!=N*(N-1)*...*2*1 (��������!). ��� ����������� ��������� Next ��������� ��������: � ����� ������ i-�� ���� ������������ ����� ���������, �� ����� ����������? �����: ���� �� ������ ������-���� �� ��������� ������ (������ � �������� ������ i).

�� ������ ����� ���������� i, ��� ������� ��� ���, �.�. ����� i, ��� X[i]<X[i+1]>...>X[N] (���� ������ i ���, �� ������������ ���������). ����� ����� X[i] ����� ��������� ���������� ��������� ��������, �.�. ����� ����� X[i+1],...,X[N] ���������� �����, ������� ���. ������� X[i] � ���, �������� ����������� ����� � �������� i+1,...,N ���, ����� ������������ ���� ����������, �� ���� � ������������ �������. ��� ����������� ���, ��� ��� ��� ����������� � ��������� �������:

	   procedure Next;
	   begin
	     {����� i: X[i]<X[i+1]>X[i+2]>...>X[N]};
	     {����� j: X[j]>X[i]>X[j+1]>...>X[N]};
	     {�������� X[i] � X[j]};
	     {X[i+1]>X[i+2]>...>X[N]};
	     {����������� X[i+1],X[i+2],...,X[N]};
	   end;

������ ����� �������� ���������:

    program Perestanovki;
      type Pere=array [byte] of byte;
      var N,i,j:byte;
	  X:Pere;
	  Yes:boolean;
      procedure Next(var X:Pere;var Yes:boolean);
	var i:byte;
	procedure Swap(var a,b:byte);  {����� ����������}
	  var c:byte;
	begin c:=a;a:=b;b:=c end;
      begin
	i:=N-1;
	{����� i}
	while (i>0)and(X[i]>X[i+1]) do dec(i);
	if i>0 then
	  begin
	    j:=i+1;
	    {����� j}
	    while (j<N)and(X[j+1]>X[i]) do inc(j);
	    Swap(X[i],X[j]);
	    for j:=i+1 to (N+i) div 2 do Swap(X[j],X[N-j+i+1]);
	    Yes:=true
	  end
	else Yes:=false
      end;
    begin
      write('N=');readln(N);
      for i:=1 to N do X[i]:=i;
      repeat
	for i:=1 to N do write(X[i]);writeln;
	Next(X,Yes)
      until not Yes
    end.

������� ����� ��������.

������ ����������� ��������� Generate(k), ������������� ��� ������������ ����� 1,...,N, � ������� ����������� ������ X[1],X[2],...,X[k]. ����� ������ �� ��������� ������ X ����� ����� �� �� ��������, ��� ����� ������ (��� �����������!). �������, ��� ��� k=N �� ����� ����� ������ ����������� ������� - ���� ������������. ��� k<N ����� ������� ������ � k+1:

	  procedure Generate(k:byte);
	    var i,j:byte;
	    procedure Swap(var a,b:byte);
	      var c:byte;
	    begin c:=a;a:=b;b:=c end;
	  begin
	    if k=N then
	      begin for i:=1 to N do write(X[i]);writeln end
	    else
	      for j:=k+1 to N do
		begin
		  Swap(X[k+1],X[j]);
		  Generate(k+1);
		  Swap(X[k+1],X[j])
		end
	  end;

�������� ���������:

	program PerestanovkiRecursion;
	  type Pere=array [byte] of byte;
	  var N,i,j:byte;
	      X:Pere;
	  procedure Generate(k:byte);
	      ...............
	begin
	  write('N=');readln(N);
	  for i:=1 to N do X[i]:=i;
	  Generate(0)
	end.

����� �� ����� ����������� � ���� ��������� ���������, �������� ��������� �� �� ������ ��� N=3. �������� ��������, ��� ������� ������ ������������ �� ����� ������������������!

����� �� ��������, � ���������� � ���������.