������ 1_03: �������������. ������������

������� ������

����� ������ ����� �������� ���������  A  ��  n  ���������.

����� ������������ ���� ���������, �. �. ������������ �� � �����-���� ������������������, ���������� �������������. ������ ��������� ���  n  ���������. ������ ���������� ����, �������� ��� ������������, ������������, ������� ���������� ����������� �������������.

���� �������� ���������  A  ��� �� ����������. ����� � �������� ��������������� ��������� ����� ����� ����� ��  1  ��  n  ��� ��  0  ��  n−1.

��������� ��������� ������������ ��  n  ��������� �����  Pn,  � ��� �������� �����  Pn.

������� �������� ��� ��� ��� �������: ���� �����  Pn,  ��� ��������� ��������  Pn,  ��� �� ��������������.



������� � ����� ������������


�������. ����� ������������ ��  n  ��������� �����  n!  — ������������ ����� �� 1 ��  n.

(�����������  n!  �������� ��-���������.)

��������������. �� ��������. ���  n = 1  ������� �������� �����.

����� ��� ����� ���  n − 1,  �������, ��� ��� ����� � ���  n.  ������ ������� ������������ ����� �������  n  ���������, � � ���������� ������� �������� �����  Pn−1  ��������� ��������� ���������. ������� ����� �������  Pn = n × Pn−1.
����  Pn−1 = (n−1)!,  ��  Pn = (n)!



��������� ������������

��� ����������� ������������, �� ��������� ���������  Pn  ����������������� (�������� �������) � ������ ���������  Tn,  �� ������� ������ ��������� ����� ������� �����, � ����� ��� ������ ��������  p ∈ Pn  � �������� ��� ������ ������� ����� ��� ������ �  Tn.

���������  Tn  — ��� ������ ������������ ���������� �������� ��������

   Tn = 0:(n−1) ´ 0:(n−2) ´´ {0}.

����� �������, ������ �������  Tn  — ��� ����� ��������������� �����  i1, i2, �, in−1, in,
������  ik £ nk.

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

������� ������������ � ������� ����� � ��� ����������� ������������. � �������� ������� ������� ������� ����� ������� �������� (������ �� ����) � ����������� ������������. ������� ������ ����������� ������������ ������ ���������� ��������. � �������� ������� ������� ������� ����� ������� �������� ������������ � ���� ������. �������� ������� �� �����.

��������, ���  k�� ������ ����� ������ �����  k�� ������, � ��������� ������ ����� ����� ����.

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



������ �����������


0 1 2 3 4 5 60 1 2 3 4 5 6������
c a d f g b ea b c d e f g2
2 a d f g b ea b d e f g0
2 0 d f g b eb d e f g1
2 0 1 f g b eb e f g2
2 0 1 2 g b eb e g2
2 0 1 2 2 b eb e0
2 0 1 2 2 0 ee0
2 0 1 2 2 0 0

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

��������� ���������  Tn

����� ������ ������������ ������������� �������� ����� ������������� ��� ������� ��������� � ���������� ����������. ��������� ������ � ��������� �� ������ ������ ��� ����������� �����-���� ������ ����� ��������:

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)(nk+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;

������ �� ���������������, ��������� ������������ ������: ����� ��������� ��� ������ �������� ��  Tn, ����� �� ������� ������ ��������������� ��� ������������.

��� �������� ������� �������� �������, ��� ���������� ������ ����� — ��� ������ ����� � ������ ������� ��������� � ���������� ���������� (������� ���������� �������������).

������� ����������� 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).

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

� ���� ������ ����� ������������� �����-�� ��������� akbk � ������ ������������ π, ��� ������� ����������� ������� �����  Σk akbπ(k). ������� � �������� �������� ���������, �����  ak  ����������� �� �����������, �  bk  — �� ��������.



������� � �������� ����� �������� ������������


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

��������������. �����������, ��� ���������� ����� ��� �������  k  �  r,  ���  ak < ar  �  bk < br.  � ���� ������

    (arak) (brbk) > 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. ��������� ������� ����������� �� ����� ���������� ��������� �����-���� �� ��������� — �������� ���������������������. ��������� �� ����������� ����� �������� ����������� �������� ������������������ �� �����������.

��������, ������������ ���������� ����� ��������������� ��� (������� ����� ����� �� ������ �������� ������������, ������� ��� ����� �� �����)
    �������
    ��������
    ��������
    ��������
    ��������
    ��������

(���������� �� ���� ��������)



����������


  1. ������� ����� ������������ ������� ��� ������� ������������ �������.

  2. �������� 10 ������������, ����������������� ��������� ����� ������������ �������.

  3. �������� ������������ ����� 15783 (������ �� 0) �� ���� ����������� �������.



��������������� �������


  1. ������������. �� ������� � ���������.

  2. ������ � �������� ���������� ������������.