|
����������: ������������� � �������.
H��������� ��� ������������ ����� 1..N.
First = (1,2,...,N)
Last = (N,N-1,...,1)
����� ����� ������������ ����� 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. �������� ��������, ��� �������
������ ������������ �� ����� ������������������!
| |