|
������ 1_03: �������������. ������������
������� ������
����� ������ ����� �������� ��������� A ��
n ���������.
����� ������������ ���� ���������, �. �. ������������ �� � �����-���� ������������������,
���������� ������������� . ������ ��������� ���
n ���������.
������ ���������� ����, �������� ��� ������������, ������������, ������� ����������
����������� ������������� .
���� �������� ��������� A ��� �� ����������.
����� � �������� ��������������� ��������� ����� ����� ����� ��
1 �� n ���
�� 0 �� n−1 .
��������� ��������� ������������ �� n ��������� �����
P n ,
� ��� �������� ����� Pn .
������� �������� ��� ��� ��� �������: ���� �����
Pn ,
��� ��������� ��������
P n ,
��� �� ��������������.
|
������� � ����� ������������
�������. ����� ������������ ��
n ��������� �����
n! — ������������ ����� ��
1 �� n .
(����������� n! �������� ��-���������.)
��������������. �� ��������. ��� n = 1
������� �������� �����.
����� ��� ����� ��� n − 1 ,
�������, ��� ��� ����� � ��� n .
������ ������� ������������ ����� ������� n ���������,
� � ���������� ������� �������� �����
Pn−1
��������� ��������� ���������. ������� ����� �������
Pn = n
× Pn−1 .
���� Pn−1 = (n−1)! ,
�� Pn = (n)!
|
��������� ������������
��� ����������� ������������, �� ��������� ���������
P n
����������������� (�������� �������) � ������ ���������
T n ,
�� ������� ������ ��������� ����� ������� �����, � ����� ��� ������ ��������
p ∈ P n
� �������� ��� ������ ������� ����� ��� ������
� T n .
��������� T n
— ��� ������ ������������ ���������� �������� ��������
T n =
0:(n−1) ´ 0:(n−2)
´ � ´ {0} .
����� �������, ������ �������
T n —
��� ����� ��������������� ����� i1 ,
i2 , �, in−1 ,
in , ������
ik £ n−k .
����, ������ �����������.
������� ������������ � ������� ����� � ��� ����������� ������������.
� �������� ������� ������� ������� ����� ������� �������� (������ �� ����) � �����������
������������. ������� ������ ����������� ������������ ������ ���������� ��������.
� �������� ������� ������� ������� ����� ������� �������� ������������ � ���� ������.
�������� ������� �� �����.
��������, ��� k �� ������ ����� ������ �����
k �� ������,
� ��������� ������ ����� ����� ����.
��������� ���� ������� �� �������.
|
������ �����������
| 0 1 2 3 4 5 6 | | 0 1 2 3 4 5 6 | | ������ |
| c a d f g b e | | a b c d e f g | | 2 |
| 2 a d f g b e | | a b d e f g | | 0 |
| 2 0 d f g b e | | b d e f g | | 1 |
| 2 0 1 f g b e | | b e f g | | 2 |
| 2 0 1 2 g b e | | b e g | | 2 |
| 2 0 1 2 2 b e | | b e | | 0 |
| 2 0 1 2 2 0 e | | e | | 0 |
| 2 0 1 2 2 0 0 | | | | |
|
��������, ��� ���� ������� ������� � ��� �������� ����������� �������� �� ������
�������� �������� ������������.
��������� ��������� T n
����� ������ ������������ ������������� �������� ����� ������������� ��� �������
��������� � ���������� ����������. ��������� ������ � ��������� �� ������ ������
��� ����������� �����-���� ������ ����� ��������:
1 ��� = 3 ����,
1 ��� = 12 ������,
1 ���� = 12 �����,
1 ����� = 6 �������.
(2, 0, 4, 2, 3) = 2 ���� 0 ����� 4 ����� 2 ����� 3 ������, ������� �� ��� �������?
����� ��������� (��� ���������� ������ ������� )
(((2 ´ 3+0) ´ 12+4) ´ 12+2)
´ 6+3 .
������� # , �������������� ������ �������� i1 ,
i2 , �, in−1 ,
in ��� �����,
�� ���������� �������� � ���� ������������ ���������
#(i1 ,
i2 , �, in−1 ,
in) = a(i1 ,
i2 , �, in−1 ,
n−1),
a(i1 ,
i2 , �, ik ,
k) = a(i1 ,
i2 , �, ik−1 ,
k−1)(n−k+1)+ ik,
a(�����,0) = 0 .
�� ���� ������� #(2,0,1,2,2,0,0) = a(2,0,1,2,2,0,6) .
����� �����
a(2,1) = 2;
a(2,0,2) = 2 ´ 6+0=12;
a(2,0,1,3) = 12 ´ 5 + 1 = 61;
a(2,0,1,2,4) = 61 ´ 4 + 2 = 246;
a(2,0,1,2,2,5) = 246 ´ 3 + 2 = 740;
a(2,0,1,2,2,0,6) = 740 ´ 2 + 0 = 1480;
������ �� ���������������, ��������� ������������ ������: ����� ��������� ��� ������
�������� �� T n ,
����� �� ������� ������ ��������������� ��� ������������.
��� �������� ������� �������� �������, ��� ���������� ������ ����� —
��� ������ ����� � ������ ������� ��������� � ���������� ���������� (������� ����������
������������� ).
������� ����������� 1 � ���� ������� ����� ��� �� ������, ��� � ��������:
�������� �� ���������� ������� �������� ��������� � ������� ������� 1.
���� ��� ��������, �� �������� 1 ������������. ���� ����������, ��������
� ������ ���� � ������� � ���������� �������.
|
������
���������� ������ �������� ����� � ������������� ������, ������� � ������-������
��������:
| 7 6 5 4 3 2 1 | | ��� ����������� ��������� |
| 3 4 4 2 1 1 0 | | ��������� �������� |
| 3 4 4 2 2 0 0 | | ���������� �� ������ ������� |
| 3 4 4 2 2 1 0 | | ���������� � ������ ������� |
| 3 4 4 3 0 0 0 | | � ������� ������� |
| 3 4 4 3 0 1 0 | | � ������ ������� |
| 3 4 4 3 1 0 0 | | �� ������ ������� |
| 3 4 4 3 1 1 0 | | � ������ ������� |
| 3 4 4 3 2 0 0 | | �� ������ ������� |
| 3 4 4 3 2 1 0 | | � ������ ������� |
| 3 5 0 0 0 0 0 | | � ����� ������� |
|
� ������ ������ ������ ����� ��, ��� � ����������, ����� ���� �������, ������
�������, . . . , � ���������� �� �����������. ������, ������ ������
����������������� ������ ���������� .
|
������� � ������������������ �������� ������������
�������. ��������� �������� ���������� ������������
� ������� ������������������� �����������.
��������������. ��� ���������� ��������, ��� ���� �� ����� ��� ������
�������� N1 �
N2 ,
� N1 ����������������� ������������
N2 , �� ������������
π(N1)
����������������� ������������ π(N2) .
��� ������������ ����������� ���������������, � ���� ���������
N1
� N2 , ��������� � �� ������������.
� �������� �������� ������� ������������� � ������� �������.
|
������ �������� ������������������� �������� ������������
����� ������������ ������������������ ������� ������������ � ���������������.
��� ����� ������� � ���� ����������� �����������.
������� �����-���� ������������ π
� ����� ������ ����������������� ���������.
������� ������ ������������ — ������ k ���������.
����� ��� ����������� �������� ����������������� �����������, � ������� ���
���������� �������� ����������� �� �����������, � ������������, � �������
��� ����������� �� ��������.
��������, � ������������ π = (4, 2, 1, 7, 3, 6, 5)
��� ����������� ��� (4, 2, 1) ����� �����
(3, 5, 6, 7) �
(7, 6, 5, 3) .
����� �� ������������ ����� ��������� �� π = (4, 2, 1, 7, 3, 6, 5) ?
�� ������ ������� ��� ����� ������� ������, ������� ����� ���������.
��������� ����������� ������ (4, 2, 1) ������ �������������,
� 3-� ������� ��� ����� �� ������. � 4-� ����. � 5-� ��������� ���������� � �����
�������.
��� ����� �� ���������� ��������� ����� ����� ��������� �� �������,
��������� ��� ����� � ��������� ����������� �����������. ���������
(4, 2, 1, 7, 5, 3, 6) .
������� ��������� ��������� ������������. � ������� ���� ��������� �� ���������� �����
(���������� �����, ��� ����� � ������), ������� — ���������� �������,
������ — �������, ������������� �� ��������.
(4 2 1 7 5 3 6)
(4 2 1 7 5 6 3)
(4 2 1 7 6 3 5)
(4 2 1 7 6 5 3)
(4 2 3 1 5 6 7)
(4 2 3 1 5 7 6)
(4 2 3 1 6 5 7)
(4 2 3 1 6 7 5)
(4 2 3 1 7 5 6)
(4 2 3 1 7 6 5)
(4 2 3 5 1 6 7)
������ ���������� ���� ������� ����.
|
���������� �������� ��������� �������� ������������
������� ���������: ������������ π
� ��������� ���������� IsActive .
��������� ���������: � π ��������
����������� ������������ � IsActive �������.
����������� ���: ���� IsActive ,
������ ������������ � �������� ����������.
�������� � �����, ����� � ������������ ���������� ��������� ��������� �������.
����� k — ������� ����� ���������.
�������� IsActive := (k > 0) .
���� IsActive , �� ����� � �������� ���������� �������,
������������� πk , �������� ���
������� � πk ,
� ����� ������� ������������� (��� ��� �������� �� ������������� ���
��������� mirror ).
|
������� ������������ ������� �����������
��� � � ������ 0-1-�������, ��������� ����� ������ �������� ������������,
��� ������� �� ������ �������� ������������ �������� �� ����������� ����.
����� ����� ���������� ����� ����� ������� ������������ ������������ — ���������
������� ���� �������� ���������.
�������� �� ����� �������? ������� ��� �������������� �����, ��� ����� ���������
������ ���.
����������� ���� n−1 ������������ �����������,
�������������� ����, ����� ������ ��������� ���������. ������ �������� �����������
����� ������� ������ ������. �� ������ ���� �������� ������ ����� ������ ��� �������.
����������� ��������, ����� ������� ������� �� ����. �� ����� ����������� ��������
���� ���, �� ����� �������� ��� ������ ��������� ��������, �������, �������, �����
��� �� ����� ������ ���� ����������� ������. ����� ����������� � ���������� ���������
��������� ������� ��������.
���������� ������
(a b c d e) ��� ��������� a
(b a c d e) ��� ��������� a
(b c a d e) ��� ��������� a
(b c d a e) ��� ��������� a
(b c d e a ) ����� ����������� a ��� ��������� b
(c b d e a ) ��� ��������� a
(c b d a e) ��� ��������� a
(c b a d e) ��� ��������� a
(c a b d e) ��� ��������� a
(a c b d e) ����� ����������� a ��� ��������� b
(a c d b e) ��� ��������� a
(c a d b e) ��� ��������� a
(c d a b e) ��� ��������� a
(c d b a e) ��� ��������� a
(c d b e a ) ����� ����������� a ��� ��������� b
(c d e b a ) ����� ����������� b ��� ��������� c
(d c e b a ) ��� ��������� a
� ��� �����.
���� �������� ����������� ����� ���������������
function ExistsNextPerm(var kCh: integer): Boolean;
var iV,iP,iVC,iPC: integer;
begin
result := False;
for iV := nV downto 2 do
if count[iV] < iV−1 then begin
Inc(count[iV]); iP := pos[iV];
iPC := iP+dir[iV]; iVC := perm[iPC];
perm[iP] := iVC; perm[iPC] := iV;
pos[iVC] := iP; pos[iV] := iPC;
kCh := iP; if dir[iV] < 0 then Dec(kCh);
result := True; exit;
end else begin
count[iV] := 0; dir[iV] := − dir[iV];
end;
end;
���� ��� �������, ������� ������� ��������� i ������������
��� ����� dir[i] — ���������� ���� (����������
�����������) � count[i] — ������� ������.
��������������� ��� ��������� � � ���, ��� ������� ����� �� �������� ������� ��
����������, � ����������� ����������. ����� ����������� ��������, �� �������� ��
�������, �� ��������� ���� ��� � ���������� ����.
|
������������� ������, ��������� � ��������������
� ���������� ���������� ��������� ����������� ������������� �����, ������� �������
� ��������������. ��� �������� ��������� ��� ��� � ����������.
|
������ � �������� ����� �������� ������������
����� ������ ��� ������ �� n �����, ������,
{ak | k ∈ 1:n} �
{bk | k ∈ 1:n} .
��� ����� ����������� �� ����
(ak, bk)
� ����������� ����� �������� ������������ ����� � ���� �����
Σk akbk .
����� ������ ��������� ��������� (ak
� bk) .
��������� ������� ����� ���������, ��� ������� ����� ����������.
� ���� ������ ����� ������������� �����-�� ��������� ak
� bk � ������ ������������ π ,
��� ������� ����������� ������� �����
Σk akbπ(k) .
������� � �������� �������� ���������, ����� ak
����������� �� �����������, � bk —
�� ��������.
|
������� � �������� ����� �������� ������������
�������. ������� ����� �������� ������������
����������� �� ����������� ������������.
��������������. �����������, ��� ���������� ����� ��� �������
k � r ,
��� ak < ar �
bk < br .
� ���� ������
(ar−ak)
(br−bk) > 0 ,
�.�. arbr + akbk >
arbk + akbr .
� ����� ��������� {ak} �����������
�� �����������. ���� {bk} �����������
�� �� �����������, �� �������� ���� k �
r , � ���������� ���� ����������.
���������� � ���� ���� bk
� br ,
�� �������� �������� �����. ������, � ����������� �������
{bk} ����� �� �����������.
��� ������� ������� ��������� ��� ����������� ��� � ����������.
|
������ � ������������ ������������ ���������������������
������ ������������������ ����� {ak | k ∈ 1:n}
����� n . ��������� ����� �� ��������������������� ����������
�����, � ������� ����� {ak} ��� �� � ������������
�������.
��������, � ������������������
3, 2 , 11 , 14 , 32, 16 , 6, 17 ,
25 , 13, 37 , 19, 41 , 12, 7, 9
������������ ����� ��������������������� ������� �����.
� �������������� ��� ������ ������� ���, ��� �������� ������������������ ����� ���� �������������.
�� ����������� ���, ��� �������, ��� �������� ��� ������, �� �������, � ������������ � �����������
��������� ����������� ����������.
������� ����� ������������������, � �� ��� �������� �������
25 14 11 33 27
29 41 15 26 32
54 87 83 15 77
91 16 35 44 23
35 37 38 12 20
29
25 14 11 33 27
29 41 15 26 32
54 87 83 15 77
91 16 35 44 23
35 37 38 12 20
29
25 14 11 33 27
29 41 15 26 32
54 87 83 15 77
91 16 35 44 23
35 37 38 12 20
29
25 14 11 33 27
29 41 15 26 32
54 87 83 15 77
91 16 35 44 23
35 37 38 12 20
29
25 14 11 33 27
29 41 15 26 32
54 87 83 15 77
91 16 35 44 23
35 37 38 12 20
29
25 14 11 33 27
29 41 15 26 32
54 87 83 15 77
91 16 35 44 23
35 37 38 12 20
29
25 14 11 33 27
29 41 15 26 32
54 87 83 15 77
91 16 35 44 23
35 37 38 12 20
29
25 14 11 33 27
29 41 15 26 32
54 87 83 15 77
91 16 35 44 23
35 37 38 12 20
29
�������� ������������������ ����������� �� ������� �� ����������� ��������:
������ ��������� ����� ������� � ����� ������� �� �������, ��� ��� �� ������� �������.
������� ����� �� ������ �������, 91. ������ ��� ����� � 8-� �������? ��� ������ 77, ���
������� � 7-� �������. � ����� 77 ������ 54. � ��� 32. � �. �.
������������������ 11, 15, 26, 32, 54, 77, 91 ���������� � ����� ����� 7.
����� ������������������ ������� ����� �������� ��� ����� �� ����� ������
(������� �������, � ��� �������� ����� ������� ��� ������ �������� ����������,
��������������� � ���������� ���������� — ���� ������� (1805-1859))
� �� ����� ���� ������������.
|
������ � ����������� ����� ��������
������ ������������������ ����� {ak | k ∈ 1:n}
����� n . ��������� ������� ����������� �� �����
���������� ��������� �����-���� �� ��������� — �������� ���������������������.
��������� �� ����������� ����� �������� ����������� �������� ������������������ �� �����������.
��������, ������������ ���������� ����� ��������������� ���
(������� ����� ����� �� ������ �������� ������������, ������� ��� ����� �� �����)
������� �
������ ��
�� ������
���� ����
��� �����
��������
(���������� �� ���� ��������)
|
����������
- ������� ����� ������������
������� ��� ������� ������������
������� .
- �������� 10 ������������, ����������������� ��������� ����� ������������
������� .
- �������� ������������ ����� 15783 (������ �� 0) �� ���� ����������� �������.
|
��������������� �������
- ������������. �� ������� � ���������.
- ������ � �������� ���������� ������������.
|
|