Описание и генерация перестановок, содержащих циклы
Запропоновано загальний підхід до генерації перестановок, що містять цикли, на основі введених конструктивних засобів опису комбінаторних множин. Формулюються та розв’язуються різні задачі генерації перестановок заданого класу. Для опису перестановок, представлених у вигляді добутку заданої кількост...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2010 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/45650 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Описание и генерация перестановок, содержащих циклы / И.В. Гребенник // Кибернетика и системный анализ. — 2010. — № 6. — С. 97–105. — Бібліогр.: 15 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859623034507231232 |
|---|---|
| author | Гребенник, И.В. |
| author_facet | Гребенник, И.В. |
| citation_txt | Описание и генерация перестановок, содержащих циклы / И.В. Гребенник // Кибернетика и системный анализ. — 2010. — № 6. — С. 97–105. — Бібліогр.: 15 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано загальний підхід до генерації перестановок, що містять цикли, на основі введених конструктивних засобів опису комбінаторних множин. Формулюються та розв’язуються різні задачі генерації перестановок заданого класу. Для опису перестановок, представлених у вигляді добутку заданої кількості циклів, вводиться комбінаторна множина. Для введеної множини будуються комбінаторний вид та відповідний твірний ряд. Наводяться приклади.
The paper proposes a general approach to generating permutations that contain cycles, based on constructive tools introduced to describe combinatorial sets. Different generation problems for permutations of definite class are formulated and solved. A combinatorial set is introduced to define permutations represented as the multiplication of a definite number of cycles. For this set, combinatorial species and associated generating series are constructed. Examples are given.
|
| first_indexed | 2025-11-29T08:16:45Z |
| format | Article |
| fulltext |
ÓÄÊ 519.85
È.Â. ÃÐÅÁÅÍÍÈÊ
ÎÏÈÑÀÍÈÅ È ÃÅÍÅÐÀÖÈß ÏÅÐÅÑÒÀÍÎÂÎÊ,
ÑÎÄÅÐÆÀÙÈÕ ÖÈÊËÛ
Êëþ÷åâûå ñëîâà: ãåíåðàöèÿ êîìáèíàòîðíûõ îáúåêòîâ, ïåðåñòàíîâêà, öèêë,
ïðîèçâåäåíèå öèêëîâ, öèêëè÷åñêàÿ ïåðåñòàíîâêà, êîìáèíàòîðíûé âèä .
ÂÂÅÄÅÍÈÅ
Çàäà÷è ãåíåðàöèè ðàçëè÷íûõ êîìáèíàòîðíûõ îáúåêòîâ ÿâëÿþòñÿ àêòóàëüíûìè â ìà-
òåìàòè÷åñêèõ èññëåäîâàíèÿõ è ïðèëîæåíèÿõ. Ãåíåðàöèè êîìáèíàòîðíûõ êîíôèãóðà-
öèé ïîñâÿùåíû ìíîãèå ìîíîãðàôèè è îòäåëüíûå ñòàòüè [1–6]. Ïîä ãåíåðàöèåé ïî-
íèìàåòñÿ ïîñòðîåíèå âñåõ êîìáèíàòîðíûõ ñòðóêòóð îïðåäåëåííîãî òèïà [3]. Ïðè
ýòîì â ëèòåðàòóðå â îñíîâíîì ðàññìàòðèâàþòñÿ âîïðîñû ãåíåðàöèè äîñòàòî÷íî ïðî-
ñòûõ îáúåêòîâ — ïåðåñòàíîâîê, ñî÷åòàíèé, ðàçáèåíèé, äåðåâüåâ, äâîè÷íûõ ïîñëåäî-
âàòåëüíîñòåé. Ðåçóëüòàòû ðåøåíèÿ çàäà÷ ãåíåðàöèè èñïîëüçóþòñÿ â ìîäåëèðîâàíèè,
êîìáèíàòîðíîé îïòèìèçàöèè è â äðóãèõ îáëàñòÿõ [7–10]. Ãåíåðàöèÿ áîëåå ñëîæíûõ
êîìáèíàòîðíûõ îáúåêòîâ çàòðóäíÿåòñÿ îòñóòñòâèåì êîíñòðóêòèâíûõ ñðåäñòâ è íåîá-
õîäèìîñòüþ çíà÷èòåëüíûõ âû÷èñëèòåëüíûõ çàòðàò, ñâÿçàííûõ ñ èçáûòî÷íîñòüþ ðå-
çóëüòàòîâ ïðèìåíåíèÿ èçâåñòíûõ ñðåäñòâ ãåíåðàöèè.
Äîñòàòî÷íî ñëîæíûå êîìáèíàòîðíûå êîíôèãóðàöèè ìîãóò áûòü ñãåíåðèðîâà-
íû ñ ïîìîùüþ êîíñòðóêòèâíûõ ñðåäñòâ îïèñàíèÿ êîìïîçèöèîííûõ k-îáðàçîâ êîì-
áèíàòîðíûõ ìíîæåñòâ, ïðåäëîæåííûõ â [11].
Ìíîãèå çàäà÷è ïåðå÷èñëèòåëüíîé êîìáèíàòîðèêè ñâÿçàíû ñ ðåøåíèåì âîïðîñà
î ñóùåñòâîâàíèè êîìáèíàòîðíûõ îáúåêòîâ çàäàííîãî òèïà è ñ îöåíêîé èõ êîëè÷åñ-
òâà [12–14].  íåêîòîðîì ñìûñëå îáðàòíûìè ê íèì ÿâëÿþòñÿ çàäà÷è ãåíåðàöèè
êîìáèíàòîðíûõ îáúåêòîâ ñ óêàçàííûìè ñâîéñòâàìè.
Îäíà èç òàêèõ «ïðÿìûõ» çàäà÷ — ïðåäñòàâëåíèå çàäàííîé ïåðåñòàíîâêè â âèäå
ïðîèçâåäåíèÿ öèêëîâ è ïîäñ÷åò êîëè÷åñòâà ïåðåñòàíîâîê çàäàííîãî òèïà [4, 12].
«Îáðàòíîé» ê íåé ÿâëÿåòñÿ çàäà÷à ãåíåðàöèè ïåðåñòàíîâîê ïî çàäàííûì öèêëàì.
Öåëü íàñòîÿùåé ñòàòüè — ïîñòàíîâêà è ðåøåíèå íåêîòîðûõ çàäà÷ ãåíåðàöèè
ïåðåñòàíîâîê, ñîäåðæàùèõ öèêëû, ñ ïðèìåíåíèåì êîíñòðóêòèâíûõ ñðåäñòâ îïèñà-
íèÿ íà îñíîâå êîìïîçèöèîííûõ k-îáðàçîâ êîìáèíàòîðíûõ ìíîæåñòâ.
ÑÏÎÑÎÁÛ ÏÐÅÄÑÒÀÂËÅÍÈß ÏÅÐÅÑÒÀÍÎÂÎÊ
Èçâåñòíû ðàçëè÷íûå ýêâèâàëåíòíûå ñïîñîáû êîìáèíàòîðíîãî ïðåäñòàâëåíèÿ ïå-
ðåñòàíîâêè ýëåìåíòîâ ìíîæåñòâà S a a an� { }1 2, , ,� (ñì., íàïðèìåð, [4, 12]).
Îäèí èç íèõ — ïðåäñòàâëåíèå ñ ïîìîùüþ îòíîøåíèÿ, ãäå â ïåðâîì ðÿäó óêàçû-
âàåòñÿ «åñòåñòâåííûé» ïîðÿäîê ýëåìåíòîâ ìíîæåñòâà S , à âî âòîðîì — íîâîå
óïîðÿäî÷åíèå:
f
a a a
a a a
n
j j jn
�
�
�
�
�
�
�
�
�
1 2
1 2
, , ... ,
, , ,�
. (1)
Äðóãîé ñïîñîá ïðåäñòàâëåíèÿ — óïîðÿäî÷åííàÿ ïîñëåäîâàòåëüíîñòü ýëåìåí-
òîâ ìíîæåñòâà S-ñëîâà:
� � ( , , , )a a aj j jn1 2
� , (2)
â êîòîðîì ïîäðàçóìåâàåòñÿ, ÷òî ïåðåñòàíîâêà ïåðåâîäèò a1 â a j1
, a2 â a j2
,
, an â a jn
.  ýòîì ñëó÷àå çàïèñü ïåðåñòàíîâêè ñîâïàäàåò ñî âòîðîé ñòðîêîé
ïðåäñòàâëåíèÿ (1).
Åùå îäèí ñïîñîá ïðåäñòàâëåíèÿ ïåðåñòàíîâêè — ýòî ïðîèçâåäåíèå öèêëîâ
� � � ��
n n nm1 2 � . Çäåñü ïîä öèêëîì äëèíû m ïåðåñòàíîâêè � íàä ìíîæåñòâîì S
ïîäðàçóìåâàåòñÿ ïîäìíîæåñòâî { }a a a Si i im1 2
, , ,� � , íà êîòîðîì ïåðåñòàíîâêà
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 97
� È.Â. Ãðåáåííèê, 2010
âûïîëíÿåò ñëåäóþùèå äåéñòâèÿ:
�( )a ai ij j
�
1
, i Jj m� , j J m� �1, �( )a ai im
�
1
, J nn � { }1 2, , ,� .
Öèêë äëèíû m ïðèíÿòî çàïèñûâàòü êàê �
m
i i ia a a
m
� ( , , , )
1 2
� . Ñëåäóÿ [12],
îáîçíà÷èì ci ÷èñëî öèêëîâ äëèíû i â çàäàííîé ïåðåñòàíîâêå �, ïðè ýòîì ïîñëåäî-
âàòåëüíîñòü ( , , , )c c cn1 2 íàçûâàåòñÿ òèïîì ïåðåñòàíîâêè �. Îáùåå ÷èñëî öèêëîâ
ïåðåñòàíîâêè � îáîçíà÷èì c c c cn( )� �
1 2 � . Ïåðåñòàíîâêó, êîòîðóþ ìîæíî
ïðåäñòàâèòü åäèíñòâåííûì öèêëîì äëèíû n, íàçûâàþò öèêëè÷åñêîé ïåðåñòà-
íîâêîé. Ïðè ýòîì êîëè÷åñòâî ïåðåñòàíîâîê òèïà ( , , , )c c cn1 2 ðàâíî
n c c n c
c c c
n
n!/ ! ! !1 21 2
1 2
� [12]. Îòìåòèì, ÷òî íåêîòîðûå ïåðå÷èñëèòåëüíûå
çàäà÷è äëÿ ïåðåñòàíîâîê òèïà ( , , , )c c cn1 2 � èññëåäîâàíû â [13].
ÊÎÍÑÒÐÓÊÒÈÂÍÛÅ ÑÐÅÄÑÒÂÀ ÎÏÈÑÀÍÈß È ÃÅÍÅÐÀÖÈÈ
Äëÿ ðåøåíèÿ ðàçëè÷íûõ çàäà÷ îïèñàíèÿ è ãåíåðàöèè ïåðåñòàíîâîê, ñîäåðæàùèõ
öèêëû, èñïîëüçóåì àïïàðàò êîìïîçèöèîííûõ k-îáðàçîâ êîìáèíàòîðíûõ ìíî-
æåñòâ [11]. Ââåäåì ñëåäóþùåå êîìáèíàòîðíîå ìíîæåñòâî.
Îïðåäåëåíèå. Êîìïîçèöèîííûé k-îáðàç êîìáèíàòîðíûõ ìíîæåñòâ Tm ;
P P P
n
c
n
c
n
c
m1 2
, , , , ïîðîæäåííûé ìíîæåñòâàìè z z z m1 2, , , , íàçîâåì êîðòåæåì
öèêëè÷åñêèõ ïåðåñòàíîâîê è îáîçíà÷èì TP N n n nc
m( , , , , )1 2 � èëè TP
N
c , ãäå
N n n nm�
1 2 .
Çäåñü T t t t t zm m j j� � �{( , , , ) |1 2
0 0
� Z , j J m� } — ìíîæåñòâî íóëåâîãî ïî-
ðÿäêà, êîðòåæ èç m ðàçëè÷íûõ ýëåìåíòîâ, z z z zm
0
1
0
2
0 0 0� �{ }, , , ,� Z Z
0 — ìíîæåñ-
òâî âñåâîçìîæíûõ êîðòåæåé èç m ðàçëè÷íûõ ýëåìåíòîâ, P
n
c
i
— ìíîæåñòâà öèêëè-
÷åñêèõ ïåðåñòàíîâîê ni ýëåìåíòîâ, i J m� — ìíîæåñòâà ïåðâîãî ïîðÿäêà;
z z z zi i i
n
i
i
� { }
1 2
, , ,� , i J m� , z zi j� � �, i j J m, � , i j� , k � 2 . Ìíîæåñòâî TP
N
c ñî-
ñòîèò èç ýëåìåíòîâ âèäà w w w w TPm N
c� �( , , , )1 2 � , ãäå w z z zi j
i
j
i
j
i
ni
� �( , , , )
1 2
�
�P
n
c
i
— öèêëè÷åñêàÿ ïåðåñòàíîâêà ýëåìåíòîâ ìíîæåñòâà z i .
Ìíîæåñòâî TP
N
c ìîæíî ïðåäñòàâèòü ñ ïîìîùüþ êîìïîçèöèè îòîáðàæåíèé
âèäà [11]:
TP z
N
c
W Tm
� � �� ( )0 , (3)
ãäå �Tm
: Z Y0 � , Y
Z
�
�
�
z
mT z
0 0
0( ) , �W : Y W� , W �
� �
�
z z P z i J
N
c
i
i ni
c i
m
TP
; ( ),0
.
Çäåñü îòîáðàæåíèå �Tm
îïèñûâàåò ïîñòðîåíèå êîðòåæà Tm èç m ðàçëè÷íûõ ýëåìåí-
òîâ, �W ñòðîèòñÿ íà îñíîâå îïåðàöèé n-çàìåùåíèÿ, n-êîìïîçèöèè è îòîáðàæåíèé
�
Pni
c , çàäàþùèõ ìíîæåñòâà öèêëè÷åñêèõ ïåðåñòàíîâîê P
n
c
i
[11]. Äëÿ ðåøåíèÿ çàäà÷
îïèñàíèÿ è ãåíåðàöèè ýëåìåíòîâ ìíîæåñòâà TP
N
c íåîáõîäèìî êîíêðåòèçèðîâàòü âèä
îòîáðàæåíèé �Tm
, �W , �
Pni
c èëè óêàçàòü ñïîñîáû èõ àëãîðèòìè÷åñêîé ðåàëèçàöèè.
Ïðîñòîòà ôîðìàëüíîãî îïèñàíèÿ è äîñòàòî÷íîå èññëåäîâàíèå ñâîéñòâ ïîçâîëÿ-
þò ðàññìàòðèâàòü êîðòåæè è öèêëè÷åñêèå ïåðåñòàíîâêè êàê áàçîâûå êîìáèíàòîð-
íûå ìíîæåñòâà [11]. Îïåðàöèè n -çàìåùåíèÿ è n -êîìïîçèöèè íàðÿäó ñ ôîðìàëüíû-
ìè îïèñàíèÿìè áàçîâûõ ìíîæåñòâ äàþò âîçìîæíîñòü ïîëó÷èòü êàê ôîðìàëüíûå
îïèñàíèÿ, òàê è ãåíåðàöèþ ýëåìåíòîâ êîðòåæà öèêëè÷åñêèõ ïåðåñòàíîâîê.
Ïîëüçóÿñü ðåçóëüòàòàìè òåîðèè êîìáèíàòîðíûõ âèäîâ [13] è ïîñòðîåííûìè
êîìáèíàòîðíûìè âèäàìè êîìïîçèöèîííûõ k-îáðàçîâ êîìáèíàòîðíûõ ìíîæåñòâ
[15], îïðåäåëèì êîìáèíàòîðíûé âèä êîðòåæà öèêëè÷åñêèõ ïåðåñòàíîâîê TP
N
c , êî-
òîðûé îáîçíà÷èì STP
N
c . Åãî ïîñòðîåíèå ïðîâåäåì ïî ñõåìå, ïðåäëîæåííîé â [15].
98 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
Ðàññìîòðèì êîìáèíàòîðíûé âèä öèêëè÷åñêèõ ïåðåñòàíîâîê C Un ii
( ) èç ni
ýëåìåíòîâ m-ìíîæåñòâà U U U Um� ( , , , )1 2 � , U z z zi
i i
n
i
i
� { }
1 2
, , ,� , i J m� [13].
Ââåäåì ìíîãîñîðòíûé âèä C U Ñ Un
i
n ii
( ) ( )� , i J m� , ñ îñíîâíûì ìíîæåñòâîì
U U U Um� ( , , , )1 2 � . Ïóñòü ST Um ( ) — m-ñîðòíûé âèä êîðòåæåé ñ îñíîâíûì ìíî-
æåñòâîì U [15]. Òîãäà êîìáèíàòîðíûé âèä STP U
N
c ( ) ìîæíî ïðåäñòàâèòü êàê
STP U ST C C C U U U
N
c
m n n n
m
m
m
( ) ( , , , )[ , , , ]� ��
1 2
1 2
1 2� �
� ST U C U C U C Um n n n
m
m
( ) ( ( ), ( ), , ( ))�
1 2
1 2
� .
Çäåñü � — îïåðàöèÿ ôóíêòîðèàëüíîé êîìïîçèöèè íà êîìáèíàòîðíûõ âèäàõ [13].
Äëÿ ðåøåíèÿ ïåðå÷èñëèòåëüíûõ çàäà÷ íà ìíîæåñòâå TP
N
c ïîñòðîèì ïðîèçâîäÿ-
ùèé ðÿä, ñâÿçàííûé ñ âèäîì STP U
N
c ( ) [13], â ñîîòâåòñòâèè ñ ïîäõîäîì, èçëîæåí-
íûì â [15]. Ó÷òåì, ÷òî èç ni ðàçëè÷íûõ ýëåìåíòîâ ìîæíî ïîñòðîèòü ( )!ni �1
öèêëè÷åñêèõ ïåðåñòàíîâîê [4, 12]. Êðîìå òîãî, áóäåì ñ÷èòàòü, ÷òî èç ýëåìåíòîâ
ìíîæåñòâà U z z zi
i i
n
i
i
� { }
1 2
, , ìîæíî ïîñòðîèòü åäèíñòâåííûé êîðòåæ Tni
�
� ( , , , )z z zi i
n
i
i1 2
� , i J m� . Òîãäà
F x x x n n n
STP n m
n n n
N
c ( , , , ) ( )! ( )! ( )!
, , ,
1 2 1 21 1 1
1 2
� �
�
� � � �
m
mx
n
x
n
x
n
n n
m
n
m�
� �
0
1
1
2
2
1 2
! ! !
�
�
�
�
n n n
n n
m
n
m
m
mx
n
x
n
x
n
1 2
1 2
0
1
1
2
2, , ,�
� . (4)
Ââåäåííîå êîìáèíàòîðíîå ìíîæåñòâî TP
N
c ïîçâîëÿåò ðåøàòü ðàçíîîáðàçíûå
çàäà÷è îïèñàíèÿ è ãåíåðàöèè ïåðåñòàíîâîê, ñîäåðæàùèõ öèêëû. Ñôîðìóëèðóåì
íåêîòîðûå èç òàêèõ çàäà÷:
1) ãåíåðàöèÿ åäèíñòâåííîé ïåðåñòàíîâêè ïî çàäàííûì âûáðàííûìè öèêëè÷åñ-
êèìè ïåðåñòàíîâêàìè öèêëàì;
2) ãåíåðàöèÿ âñåõ ïåðåñòàíîâîê ïî öèêëàì, çàäàííûì âñåâîçìîæíûìè öèêëè-
÷åñêèìè ïåðåñòàíîâêàìè ýëåìåíòîâ ìíîæåñòâ U z z zi
i i
n
i
i
� { }
1 2
, , ,� , i J m� ;
3) ãåíåðàöèÿ âñåõ ïåðåñòàíîâîê, ñîäåðæàùèõ öèêëû, ïîðîæäåííûõ ìíîæåñ-
òâîì, ñîñòîÿùèì èç N ðàçëè÷íûõ ýëåìåíòîâ.
Ïðîàíàëèçèðóåì ñôîðìóëèðîâàííûå çàäà÷è.
ÃÅÍÅÐÀÖÈß ÏÅÐÅÑÒÀÍÎÂÊÈ ÏÎ ÇÀÄÀÍÍÛÌ ÖÈÊËÀÌ
Çàäà÷à 1. Çàäàíû êîëè÷åñòâî m è ÿâíûé âèä öèêëîâ � � �
n n nm1 2, , ,� , ïî-
ðîæäåííûõ íåïåðåñåêàþùèìèñÿ ìíîæåñòâàìè ðàçëè÷íûõ ýëåìåíòîâ
z z z zi i i
n
i
i
� { }
1 2
, , ,� , i J m� . Ïóñòü n n nm1 2, , ,� — äëèíû öèêëîâ, à n n1 2
�
�
�n Nm . Íåîáõîäèìî ñãåíåðèðîâàòü ïåðåñòàíîâêó � �PN , êîòîðàÿ ïðåäñòàâëÿ-
åòñÿ ïðîèçâåäåíèåì öèêëîâ � � �
n n nm1 2, , ,� . Çäåñü PN — ìíîæåñòâî ïåðåñòàíîâîê
èç N ðàçëè÷íûõ ýëåìåíòîâ, à ïîä ÿâíûì çàäàíèåì öèêëà �
ni ïîäðàçóìåâàåòñÿ
z z z z
j
i
j
i
j
i
j
i
ni1 2 1
� � � � � , j Jk ni
� , k J ni
� , i J m� . (5)
Îòìåòèì, ÷òî òèï çàäàííîé òàêèì îáðàçîì ïåðåñòàíîâêè � ïîëíîñòüþ
îïðåäåëÿåòñÿ äëèíàìè öèêëîâ, à ñàìè öèêëû ìîæíî ðàññìàòðèâàòü êàê ýëåìåíòû
ìíîæåñòâ öèêëè÷åñêèõ ïåðåñòàíîâîê P
n
c
i
, ïîðîæäåííûõ ìíîæåñòâàìè
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 99
z z z zi i i
n
i
i
� { }
1 2
, , ,� , i J m� . Äëÿ ïîëó÷åíèÿ èñêîìîé ïåðåñòàíîâêè � âîñïîëüçóåìñÿ
ïîñòðîåííûì âûøå êîðòåæåì öèêëè÷åñêèõ ïåðåñòàíîâîê TP
N
c . Èç ñïîñîáà ïîñòðîå-
íèÿ ìíîæåñòâà TP
N
c ñëåäóåò, ÷òî ïåðåñòàíîâêà � ÿâëÿåòñÿ îäíèì èç åãî ýëåìåíòîâ.
Åãî ìîæíî ïîëó÷èòü ñëåäóþùèì îáðàçîì.
Äëÿ îïðåäåëåííîñòè áóäåì ñ÷èòàòü, ÷òî ýëåìåíòû ìíîæåñòâà z i óïîðÿäî÷åíû:
z z zi i
n
i
i1 2
� � �� , i J m� . Öèêëè÷åñêóþ ïåðåñòàíîâêó ýëåìåíòîâ ìíîæåñòâà z i ,
îïðåäåëÿåìóþ öèêëîì �
ni âèäà (4), çàïèøåì
f
z z z
z z z
i
i i
n
i
l
i
l
i
l
i
i
ni
�
�
�
�
�
�
�
�
�
�
�
1 2
1 2
�
�
(6)
èëè â âèäå óïîðÿäî÷åííîé ïîñëåäîâàòåëüíîñòè, òîëüêî âòîðîé ñòðîêîé
( , , , )z z z
l
i
l
i
l
i
ni1 2
� , (7)
ïîäðàçóìåâàÿ, ÷òî ïåðåñòàíîâêà ïåðåâîäèò z i
1
â z
l
i
1
, z i
2
â z
l
i
2
, …, z
n
i
i
â z
l
i
ni
. Óêà-
çàííîå ïðåäñòàâëåíèå öèêëè÷åñêîé ïåðåñòàíîâêè, îïðåäåëÿåìîé öèêëîì �
ni , ïî-
ëó÷èì ñ ïîìîùüþ àëãîðèòìà 1, êîòîðûé âûïîëíÿåò ïðîõîä ïî öåïî÷êå (5) è
ôîðìèðóåò öèêëè÷åñêóþ ïåðåñòàíîâêó.
Àëãîðèòì 1. Ôîðìèðîâàíèå öèêëè÷åñêîé ïåðåñòàíîâêè â âèäå óïîðÿäî÷åííîé
ïîñëåäîâàòåëüíîñòè íà îñíîâå öèêëà äëèíû ni .
Çàäàíû: öèêë �
ni äëèíû ni â âèäå (5). Ðåçóëüòàò: öèêëè÷åñêàÿ ïåðåñòàíîâêà
b b b bi i i
n
i
i
� ( , , , )
1 2
� â âèäå (6) èëè (7).
1. Óñòàíîâèòü k � 1, s � 1.
2. Íàéòè j kl � â ïîñëåäîâàòåëüíîñòè { }j j jni1 2, , ... , .
3. Ïðèñâîèòü b z
k
i
j
i
l
�
1
, åñëè l ni� , èíà÷å ïåðåéòè ê ï. 6.
4. Çàäàòü l l�
1, k jl� , s s�
1.
5. Ïåðåéòè ê ï. 3, åñëè s ni� , èíà÷å — îñòàíîâ.
6. Ïðèñâîèòü b z
k
i
j
i�
1
, l � 1, s s�
1, k j� 1, ïåðåéòè ê ï. 3.
Ðåçóëüòàò ðàáîòû àëãîðèòìà — öèêëè÷åñêàÿ ïåðåñòàíîâêà b b b bi i i
n
i
i
� ( , , ... , )
1 2
èëè
f
z z z
z z z
i
i i
n
i
l
i
l
i
l
i
i
ni
�
�
�
�
�
�
�
�
�
�
�
1 2
1 2
�
�
,
ñîîòâåòñòâóþùàÿ öèêëó �
nj .
Äëÿ ïîëó÷åíèÿ ïåðåñòàíîâêè � îáúåäèíèì â êîðòåæ âñå öèêëè÷åñêèå ïåðåñòà-
íîâêè, ïîëó÷åííûå ñ ïîìîùüþ àëãîðèòìà 1 äëÿ âñåõ öèêëîâ �
ni , i J m� . Ïðè ýòîì
íåîáõîäèìî ñôîðìèðîâàòü ìíîæåñòâî ýëåìåíòîâ Z, ïîðîæäàþùèõ ïåðåñòàíîâêó �,
è çàäàòü íà íåì «åñòåñòâåííûé» ïîðÿäîê ýëåìåíòîâ, ò.å. ñôîðìèðîâàòü ïåðâóþ
ñòðîêó â ïðåäñòàâëåíèè (1). Äëÿ ýòîãî âîñïîëüçóåìñÿ àëãîðèòìîì 2.
Àëãîðèòì 2. Ôîðìèðîâàíèå ïåðåñòàíîâêè �, ÿâëÿþùåéñÿ ïðîèçâåäåíèåì öèê-
ëîâ � � �
n n nm1 2, , .
Çàäàíû: öèêëè÷åñêèå ïåðåñòàíîâêè b b bm1 2, , ... , , ïîëó÷åííûå ñîîòâåòñòâåííî
èç öèêëîâ � � �
n n nm1 2, , ,� ñ ïîìîùüþ àëãîðèòìà 1. Ðåçóëüòàò: ïåðåñòàíîâêà
� � ( , , ... , )p p p N1 2 â âèäå (1) è (2) ÿâëÿåòñÿ ïðîèçâåäåíèåì öèêëîâ
� � �
n n nm1 2, , ,� . Çäåñü p
k
1 — ýëåìåíò ïåðâîãî, à p
k
2 — ýëåìåíò âòîðîãî ðÿäà ïåðå-
ñòàíîâêè � â ïðåäñòàâëåíèè (1), k J N� .
100 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
1. Óñòàíîâèòü i � 1 — ñ÷åò÷èê öèêëîâ �
ni , s � 0 .
2. Óñòàíîâèòü k � 1 — ñ÷åò÷èê ýëåìåíòîâ âíóòðè öèêëà.
3. Ïðèñâîèòü p z
k s k
i
�1 , p f z b
k s
i
k
i
k
i
� �2 ( ) .
4. Çàäàòü k k�
1. Ïåðåéòè ê ï. 3, åñëè k ni� , èíà÷å — ê ï. 5.
5. Ïðèñâîèòü s s ni�
, i i�
1.
6. Ïåðåéòè ê ï. 2, åñëè i m� , èíà÷å — îñòàíîâ.
Òàêèì îáðàçîì, ïîñëåäîâàòåëüíîå ïðèìåíåíèå àëãîðèòìà 1 äëÿ êàæäîãî öèêëà
�
ni , i J m� , è àëãîðèòìà 2 äëÿ ïîëó÷åííûõ öèêëè÷åñêèõ ïåðåñòàíîâîê b b bm1 2, , ... ,
ïîçâîëÿåò ðåøèòü çàäà÷ó 1. Ðàññìîòðèì ïðèìåðû.
Ïðèìåð 1. Çàäàíû m � 2 öèêëà, ïîðîæäåííûå ìíîæåñòâàìè z a b c d1 � { }, , , è
z e f g2 � { }, , , �
4: b d a c b� � � � , �
3 : f e g f� � � . Ñãåíåðèðîâàòü ïåðåñòà-
íîâêó � �P7 , êîòîðàÿ ÿâëÿåòñÿ ïðîèçâåäåíèåì çàäàííûõ öèêëîâ.
Èñïîëüçóÿ àëãîðèòì 1, ïîñòðîèì öèêëè÷åñêèå ïåðåñòàíîâêè b1 è b2 â âèäå (6)
è (7) èç öèêëîâ �
4 è �
3 :
f
a b c d
c d b a
b c d b a f
e f g
g e f
b1 1 2 2�
�
�
��
�
�
�� � �
�
�
��
�
�
��, ( ), , � ( )g e f .
Ñ ïîìîùüþ àëãîðèòìà 2 ïîëó÷èì èñêîìóþ ïåðåñòàíîâêó � �P7 , ïîðîæäåííóþ
ìíîæåñòâîì Z a b c d e f g� { }, , , , , , :
f
a b c d e f g
c d b a g e f
c d b a g e f�
��
�
�
��
�
�
�� �, ( ).
Ïðèìåð 2. Çàäàíû m � 2 öèêëà, ïîðîæäåííûå ìíîæåñòâàìè z1 3 5 7� { }, , è
z 2 12 4 6� { }, , , , �
3 7 3 5 7: � � � , �
4 2 4 1 6 2: � � � � . Ñãåíåðèðîâàòü ïåðåñòà-
íîâêó � �P7 , êîòîðàÿ ÿâëÿåòñÿ ïðîèçâåäåíèåì çàäàííûõ öèêëîâ.
Ïî àëãîðèòìó 1 ïîñòðîèì öèêëè÷åñêèå ïåðåñòàíîâêè b1 è b2 â âèäå (6) è (7) èç
öèêëîâ �
3 è �
4 :
f b f b1 1 2 23 5 7
5 7 3
5 7 3
1 2 4 6
6 4 1 2
�
�
�
��
�
�
�� � �
�
�
��
�
�
�� �, ( ), , ( )6 4 1 2 .
Ïîëüçóÿñü àëãîðèòìîì 2, ïîëó÷èì ïåðåñòàíîâêó � �P7 , ïîðîæäåííóþ ìíî-
æåñòâîì Z � { }1 2 3 4 5 6 7, , , , , , :
f � �
�
�
��
�
�
��
3 5 7 1 2 4 6
5 7 3 6 4 1 2
, � � ( )5 7 3 6 4 1 2 .
(8)
Îòìåòèì, ÷òî, ïåðåóïîðÿäî÷èâàÿ ýëåìåíòû ïåðâîé ñòðîêè f � âìåñòå ñ ñîîòâå-
òñòâóþùèìè ýëåìåíòàìè âòîðîé ñòðîêè, ïîëó÷èì ïåðåñòàíîâêó, ÿâëÿþùóþñÿ ïðî-
èçâåäåíèåì òåõ æå öèêëîâ, ÷òî è �:
f
� 1
1 2 3 4 5 6 7
6 4 5 1 7 2 3
�
�
�
��
�
�
�� , �1 6 4 5 1 7 2 3� ( ) .
(9)
ÃÅÍÅÐÀÖÈß ÂÑÅÕ ÏÅÐÅÑÒÀÍÎÂÎÊ ÏÎ ÖÈÊËÀÌ, ÏÎÐÎÆÄÅÍÍÛÌ
ÇÀÄÀÍÍÛÌÈ ÌÍÎÆÅÑÒÂÀÌÈ
Çàäà÷à 2. Çàäàíû m íåïåðåñåêàþùèõñÿ ìíîæåñòâ ðàçëè÷íûõ ýëåìåíòîâ
z z z zi i i
n
i
i
� { }
1 2
, , ,� , i J m� . Ìíîæåñòâà z i ïîðîæäàþò ìíîæåñòâà öèêëè÷åñêèõ
ïåðåñòàíîâîê P z
n
c i
i
( ) , i J m� . Êàæäàÿ öèêëè÷åñêàÿ ïåðåñòàíîâêà p P zj
n
c i
i
� ( ) ,
j J Mi
� , M ni i� �( )!1 , îïðåäåëÿåò åäèíñòâåííûé öèêë �
n ji p( ) . Íåîáõîäèìî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 101
ñãåíåðèðîâàòü âñå âîçìîæíûå ðàçëè÷íûå ïåðåñòàíîâêè � �PN ,
n n n Nm1 2
�� , êîòîðûå ïðåäñòàâëÿþòñÿ â âèäå ïðîèçâåäåíèÿ öèêëîâ
�
n ji p( ) , j J Mi
� , M ni i� �( )!1 , i J m� .
Êàê ñëåäóåò èç [4, 12], ïîñêîëüêó ìíîæåñòâà z i , i J m� , à çíà÷èò, è îïðåäåëÿå-
ìûå èìè öèêëû íå ïåðåñåêàþòñÿ, òî ïîðÿäîê ñëåäîâàíèÿ öèêëîâ ïðè ïðåäñòàâëåíèè
ïåðåñòàíîâêè â âèäå ïðîèçâåäåíèÿ öèêëîâ íå èìååò çíà÷åíèÿ. Ïîýòîìó â ðàìêàõ
ðàññìàòðèâàåìîé çàäà÷è íå áóäåì ðàçëè÷àòü ïåðåñòàíîâêè, êîòîðûå ïðåäñòàâëÿþò-
ñÿ â âèäå ïðîèçâåäåíèÿ îäèíàêîâûõ öèêëîâ, íàïðèìåð ïåðåñòàíîâêè (8) è (9). Êðî-
ìå òîãî, ëþáûå öèêëè÷åñêèå ñäâèãè ýëåìåíòîâ ïðè çàäàíèè öèêëîâ íå èçìåíÿþò ðå-
çóëüòàòà ãåíåðàöèè ïåðåñòàíîâêè �. Ïîýòîìó, ãîâîðÿ î ãåíåðàöèè âñåõ âîçìîæíûõ
ðàçëè÷íûõ ïåðåñòàíîâîê â äàííîé çàäà÷å, èìåþòñÿ â âèäó òîëüêî òå èç íèõ, êîòî-
ðûå ïðåäñòàâëÿþòñÿ ïðîèçâåäåíèÿìè ðàçëè÷íûõ ïî ñîñòàâó è (èëè) ïîðÿäêó ñëåäî-
âàíèÿ ýëåìåíòîâ öèêëîâ. Êàæäûé òàêîé öèêë �
n ji p( ) îäíîçíà÷íî îïðåäåëÿåòñÿ
öèêëè÷åñêîé ïåðåñòàíîâêîé p P zj
n
c i
i
� ( ) , j J Mi
� , M ni i� �( )!1 [4, 12]. Êîëè÷å-
ñòâî öèêëîâ, ïîðîæäàåìûõ ìíîæåñòâîì z i , ðàâíî êîëè÷åñòâó ðàçëè÷íûõ öèêëè-
÷åñêèõ ïåðåñòàíîâîê, êîòîðûå ìîæíî ïîñòðîèòü èç ýëåìåíòîâ ìíîæåñòâà z i . À êî-
ëè÷åñòâî ðàçëè÷íûõ ïåðåñòàíîâîê, êîòîðûå ìîæíî ïðåäñòàâèòü â âèäå ïðîèçâåäå-
íèÿ öèêëîâ èç ýëåìåíòîâ çàäàííûõ ìíîæåñòâ, ðàâíî êîëè÷åñòâó ýëåìåíòîâ êîðòåæà
öèêëè÷åñêèõ ïåðåñòàíîâîê TP
N
c , ââåäåííîãî âûøå. Óêàçàííîå êîëè÷åñòâî ýëåìåí-
òîâ ìîæíî îïðåäåëèòü ñ ïîìîùüþ ïðîèçâîäÿùåãî ðÿäà (4). Òàêèì îáðàçîì, ñôîð-
ìóëèðîâàííóþ çàäà÷ó 2 ìîæíî çàìåíèòü ýêâèâàëåíòíîé åé çàäà÷åé ãåíåðàöèè âñåõ
ýëåìåíòîâ êîðòåæà öèêëè÷åñêèõ ïåðåñòàíîâîê.
Ïîñêîëüêó êîðòåæ öèêëè÷åñêèõ ïåðåñòàíîâîê ïðåäñòàâëÿåò ñîáîé êîìïîçèöè-
îííûé k-îáðàç êîìáèíàòîðíûõ ìíîæåñòâ, òî îïèñàíèå è ãåíåðàöèÿ åãî ýëåìåíòîâ
ìîãóò âûïîëíÿòüñÿ ñ ïîìîùüþ îòîáðàæåíèé íà îñíîâå áàçîâûõ êîìáèíàòîðíûõ
ìíîæåñòâ êîðòåæåé è öèêëè÷åñêèõ ïåðåñòàíîâîê [11]. Ïðè ðåøåíèè çàäà÷ ãåíåðà-
öèè ïåðåñòàíîâîê, ñîäåðæàùèõ öèêëû, áóäåì îðèåíòèðîâàòüñÿ íà àëãîðèòìè÷åñ-
êóþ ðåàëèçàöèþ îòîáðàæåíèé �Tm
, �W , �
Pni
c , îïèñûâàþùèõ ýëåìåíòû ìíîæåñòâà
TP
N
c â ñîîòíîøåíèè (3).
Ïðè ðåàëèçàöèè îòîáðàæåíèÿ �W êàæäûé ýëåìåíò ìíîæåñòâà íóëåâîãî ïîðÿä-
êà — êîðòåæà Tm — çàìåíÿåòñÿ îäíèì èç ýëåìåíòîâ ìíîæåñòâ öèêëè÷åñêèõ ïåðåñòà-
íîâîê P z P z P z
n
c
n
c
n
c m
m1 2
1 2( ), ( ), , ( )� ñîîòâåòñòâåííî. Â ðåçóëüòàòå ôîðìèðóåòñÿ îäèí
ýëåìåíò ìíîæåñòâà TP
N
c — ïåðåñòàíîâêà �, îáëàäàþùàÿ òðåáóåìûìè ñâîéñòâàìè.
Äëÿ ïîëó÷åíèÿ âñåõ ýëåìåíòîâ ìíîæåñòâà TP
N
c îïèñàííûì ñïîñîáîì îòîáðà-
æåíèå �
Tm
ðåàëèçóåì àëãîðèòìè÷åñêè. Îòîáðàæåíèå �
Pni
c ïîëó÷èì íà îñíîâå èñ-
ïîëüçîâàíèÿ ìåòîäà ãåíåðàöèè ýëåìåíòîâ ìíîæåñòâà öèêëè÷åñêèõ ïåðåñòàíîâîê.
Îäèí èç àëãîðèòìîâ ãåíåðàöèè öèêëè÷åñêèõ ïåðåñòàíîâîê îïèñàí â [1]. Ïðèìåíå-
íèå äàííîãî àëãîðèòìà ïîçâîëÿåò ãåíåðèðîâàòü âñå ýëåìåíòû áàçîâûõ êîìáèíàòîð-
íûõ ìíîæåñòâ öèêëè÷åñêèõ ïåðåñòàíîâîê. Ñãåíåðèðîâàâ ïî îäíîìó ýëåìåíòó ìíî-
æåñòâ P z
n
c
1
1( ) , P z P z
n
c
n
c m
m2
2( ), , ( ) , ïîëó÷èì m öèêëîâ. Ñ ïîìîùüþ àëãîðèòìà 2,
ðåàëèçóþùåãî îòîáðàæåíèå �W , îíè ìîãóò áûòü ïðåîáðàçîâàíû â ïåðåñòàíîâêó �,
êîòîðóþ ìîæíî ïðåäñòàâèòü â âèäå ïðîèçâåäåíèÿ óêàçàííûõ öèêëîâ.
Òàêèì îáðàçîì, ðåøåíèå çàäà÷è 2 ñâîäèòñÿ ê ìíîãîêðàòíîìó ðåøåíèþ çàäà-
÷è 1 íà îñíîâå ãåíåðàöèè ýëåìåíòîâ ìíîæåñòâ öèêëè÷åñêèõ ïåðåñòàíîâîê â ñîîò-
âåòñòâèè ñ âûáðàííîé ñõåìîé. Ðàññìîòðèì ïðèìåð.
Ïðèìåð 3. Çàäàíû m � 2 íåïåðåñåêàþùèåñÿ ìíîæåñòâà z1 3 5 7� { }, , è
z 2 1 2 4 6� { }, , , , ïîðîæäàþùèå ìíîæåñòâà öèêëè÷åñêèõ ïåðåñòàíîâîê P z
n
c
1
1( ) , P z
n
c
2
2( ) .
Ñãåíåðèðîâàòü âñå âîçìîæíûå ðàçëè÷íûå ïåðåñòàíîâêè � �P7 , êîòîðûå ïðåäñòàâ-
ëÿþòñÿ â âèäå ïðîèçâåäåíèÿ öèêëîâ �
n ji p( ) , j J Mi
� , M ni i� �( )!1 , i J� 2 .
102 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
Êàê îòìå÷åíî âûøå, êîëè÷åñòâî öèêëè÷åñêèõ ïåðåñòàíîâîê (à çíà÷èò, è
öèêëîâ), ñîñòàâëåííûõ èç n ýëåìåíòîâ, ðàâíî ( )!n �1 . Èç ìíîæåñòâà z1 ìîæíî
ïîñòðîèòü äâà ðàçëè÷íûõ öèêëà �
n1 : 3 5 7 3� � � , 3 7 5 3� � � . Èç ìíîæåñ-
ò â à z 2 — 6 öèêëîâ �
n2 : 1 2 4 6 1� � � � , 1 4 2 6 1� � � � ,
1 2 6 4 1� � � � , 1 4 6 2 1� � � � , 1 6 2 4 1� � � � , 1 6 4 2 1� � � � .
Ìîæíî ïîñòðîèòü 12 ðàçëè÷íûõ ïåðåñòàíîâîê, êîòîðûå ïðåäñòàâëÿþòñÿ â âèäå ïðî-
èçâåäåíèÿ öèêëîâ �
n1 è �
n2 . Êîìáèíèðóÿ ðàçëè÷íûå ïàðû öèêëîâ �
n1 è �
n2 , ïîëó-
÷èì 12 âàðèàíòîâ èñõîäíûõ äàííûõ äëÿ çàäà÷è 1. Âûïîëíÿÿ â êàæäîì ñëó÷àå äåé-
ñòâèÿ â ñîîòâåòñòâèè ñ àëãîðèòìàìè 1 è 2, ïîëó÷èì 12 ïåðåñòàíîâîê âèäà (6):
3 5 7 1 2 4 6
5 7 3 2 4 6 1
3 5 7 1 2 4 6
5 7 3 4 6 2 1
3 5 7 1�
�
��
�
�
��
�
�
��
�
�
��, ,
2 4 6
5 7 3 4 6 1 4
3 5 7 1 2 4 6
5 7 3 4 1 6 2
�
�
��
�
�
��
�
�
��
�
�
��, ,
3 5 7 1 2 4 6
5 7 3 6 4 1 2
3 5 7 1 2 4 6
5 7 3 6 1 2 4
3 5 7 1�
�
��
�
�
��
�
�
��
�
�
��, ,
2 4 6
7 3 5 2 4 6 1
3 5 7 1 2 4 6
7 3 5 4 6 2 1
�
�
��
�
�
��
�
�
��
�
�
��, ,
3 5 7 1 2 4 6
7 3 5 2 6 1 4
3 5 7 1 2 4 6
7 3 5 4 1 6 2
3 5 7 1�
�
��
�
�
��
�
�
��
�
�
��, ,
2 4 6
7 3 5 6 4 1 2
3 5 7 1 2 4 6
7 3 5 6 1 2 4
�
�
��
�
�
��
�
�
��
�
�
��, .
ÃÅÍÅÐÀÖÈß ÂÑÅÕ ÏÅÐÅÑÒÀÍÎÂÎÊ, ÏÎÐÎÆÄÅÍÍÛÕ ÐÀÇÁÈÅÍÈßÌÈ ÌÍÎÆÅÑÒÂÀ
Çàäà÷à 3. Çàäàíî ìíîæåñòâî Z z z z N� { }1 2, , ,� , ñîñòîÿùåå èç ðàçëè÷íûõ ýëå-
ìåíòîâ. Ïîëàãàåì, ÷òî ìíîæåñòâî Z ðàçáèâàåòñÿ íà íåïåðåñåêàþùèåñÿ ïîäìíî-
æåñòâà z z z zik ik ik
n
ik
i
� { }
1 2
, , ,� , i J mk
� , n n n Nmk1 2
�� , k J K� , ãäå K — êî-
ëè÷åñòâî âàðèàíòîâ ðàçáèåíèÿ ìíîæåñòâà Z íà íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà.
Êàæäîå ïîäìíîæåñòâî z ik ïîðîæäàåò ìíîæåñòâî öèêëè÷åñêèõ ïåðåñòàíîâîê
P z
n
c ik
i
( ) è ìíîæåñòâî ñîîòâåòñòâóþùèõ öèêëîâ �
n ji p( ) , j J Mi
� , M ni i� �( )!1 .
Íåîáõîäèìî ñãåíåðèðîâàòü âñå âîçìîæíûå ðàçëè÷íûå ïåðåñòàíîâêè ýëåìåíòîâ
ìíîæåñòâà Z , � �PN , êîòîðûå ïðåäñòàâëÿþòñÿ â âèäå ïðîèçâåäåíèÿ öèêëîâ
�
n ji p( ) , ïîðîæäåííûõ âñåâîçìîæíûìè öèêëè÷åñêèìè ïåðåñòàíîâêàìè:
p P zj
n
c ik
i
� ( ) , j J Mi
� , M ni i� �( )!1 , k J K� .
Ìåõàíèçì ãåíåðàöèè ïåðåñòàíîâîê â äàííîé çàäà÷å ìîæåò áûòü îñíîâàí íà ðå-
øåíèè çàäà÷è 2 äëÿ êàæäîãî âàðèàíòà ðàçáèåíèÿ ìíîæåñòâà Z íà íåïåðåñåêàþùèå-
ñÿ ïîäìíîæåñòâà. Êàæäûé âàðèàíò ðàçáèåíèÿ z z z zik ik ik
n
ik
i
� { }
1 2
, , ,� , i J mk
� ,
n n n Nmk1 2
�� , k J K� , ïîðîæäàåò ìíîæåñòâà öèêëè÷åñêèõ ïåðåñòàíîâîê
P z
n
c ik
i
( ) , j J Mi
� , M ni i� �( )!1 è ñîîòâåòñòâóþùèå öèêëû �
n ji p( ) ,
p P zj
n
c ik
i
� ( ) , êîòîðûå ÿâëÿþòñÿ èñõîäíûìè äàííûìè äëÿ çàäà÷è 2. Òàêèì îáðà-
çîì, äëÿ ðåøåíèÿ çàäà÷è 3 íåîáõîäèìî îïðåäåëèòü ñïîñîá ãåíåðàöèè
âñåâîçìîæíûõ ðàçáèåíèé ìíîæåñòâà Z íà íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà.
Çàäà÷à ðàçáèåíèÿ ìíîæåñòâà íà ïîäìíîæåñòâà ÿâëÿåòñÿ êëàññè÷åñêîé â êîìáè-
íàòîðèêå [2, 3, 5, 12]. Ðàçëè÷íûì âàðèàíòàì ðàçáèåíèé ìíîæåñòâà íà íåïåðåñåêàþ-
ùèåñÿ íåïóñòûå ïîäìíîæåñòâà (áëîêè) ñîîòâåòñòâóþò êîëè÷åñòâåííûå îöåíêè.
×èñëî ðàçáèåíèé n -ìíîæåñòâà íà k áëîêîâ îöåíèâàåòñÿ ÷èñëîì Ñòèðëèíãà âòîðîãî
ðîäà S n k( , ) , à îáùåå ÷èñëî ðàçáèåíèé n -ìíîæåñòâà — ÷èñëîì Áåëëà B n( ) , ãäå
B n S n k
k
n
( ) ( , )�
�
�
1
. Àëãîðèòìû ãåíåðàöèè ðàçáèåíèé ìíîæåñòâà íà áëîêè îïèñàíû
â [2, 5] è îðèåíòèðîâàíû êàê íà ãåíåðàöèþ âñåâîçìîæíûõ ðàçáèåíèé (àëãîðèòì
Õàò÷èíñîíà), òàê è ðàçáèåíèé n -ìíîæåñòâà òî÷íî íà k áëîêîâ. Èñïîëüçîâàíèå óêàçàí-
íûõ àëãîðèòìîâ ïîçâîëÿåò ôîðìèðîâàòü ìíîæåñòâà, ïîðîæäàþùèå öèêëû, äëÿ çàäà÷è
ãåíåðàöèè ïåðåñòàíîâîê, êîòîðûå ìîæíî ïðåäñòàâèòü â âèäå ïðîèçâåäåíèÿ öèêëîâ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 103
Ïðè ýòîì ìîæíî ðàññìàòðèâàòü âàðèàíò çàäà÷è ïðåäñòàâëåíèÿ ïåðåñòàíîâêè
â âèäå ïðîèçâåäåíèÿ â òî÷íîñòè k öèêëîâ è ïðîèçâåäåíèÿ ðàçëè÷íîãî ÷èñëà öèêëîâ
(ïî ÷èñëó ïîäìíîæåñòâ, íà êîòîðûå ðàçáèâàåòñÿ ìíîæåñòâî Z ). Êîëè÷åñòâî ïåðå-
ñòàíîâîê, èìåþùèõ â òî÷íîñòè k öèêëîâ, îöåíèâàåòñÿ ÷èñëîì Ñòèðëèíãà ïåðâîãî
ðîäà s n k( , ) [12]. Òàêæå ìîæíî ðåøèòü çàäà÷ó ãåíåðàöèè âñåõ ïåðåñòàíîâîê çàäàí-
íîãî òèïà èç ýëåìåíòîâ ìíîæåñòâà Z. Äëÿ ýòîãî ïðè ãåíåðàöèè ðàçáèåíèé ìíîæåñ-
òâà Z íà ïîäìíîæåñòâà íåîáõîäèìî âûáèðàòü òîëüêî òå âàðèàíòû ðàçáèåíèé, êîòî-
ðûå ïî êîëè÷åñòâó ïîäìíîæåñòâ ðàçíîé ìîùíîñòè ñîîòâåòñòâóþò çàäàííîìó òèïó
ïåðåñòàíîâêè. Âî âñåõ ýòèõ ñëó÷àÿõ ðàññìîòðåííûå âûøå çàäà÷è 1 è 2 ìîæíî ðàñ-
ñìàòðèâàòü êàê áàçîâûå çàäà÷è ãåíåðàöèè ïåðåñòàíîâîê, ñîäåðæàùèõ öèêëû. Ê íèì
òåì èëè èíûì ñïîñîáîì ñâîäÿòñÿ âñå áîëåå îáùèå çàäà÷è ãåíåðàöèè ïåðåñòàíîâîê
óêàçàííîãî êëàññà.
ÎÖÅÍÊÀ ÌÅÒÎÄÀ ÃÅÍÅÐÀÖÈÈ ÏÅÐÅÑÒÀÍÎÂÎÊ, ÑÎÄÅÐÆÀÙÈÕ ÖÈÊËÛ
Îòìåòèì, ÷òî ìíîæåñòâî PN , ïîðîæäåííîå îáúåäèíåíèåì ìíîæåñòâ ïîðîæäàþ-
ùèõ ýëåìåíòîâ öèêëè÷åñêèõ ïåðåñòàíîâîê
~
Z z i
i
m
�
�1
� , ñîäåðæèò âñå ýëåìåíòû êîð-
òåæà öèêëè÷åñêèõ ïåðåñòàíîâîê TP
N
c . Ïîýòîìó âñå ïåðåñòàíîâêè, óäîâëåòâîðÿþ-
ùèå óñëîâèÿì çàäà÷ 1, 2, ìîæíî îñóùåñòâèòü ãåíåðàöèåé ïåðåñòàíîâîê âñåõ ýëå-
ìåíòîâ ìíîæåñòâà
~
Z è ïðîâåðêîé êàæäîãî èç íèõ íà äîïóñòèìîñòü ñ ïîìîùüþ
ðàçëîæåíèÿ íà ïðîèçâåäåíèå öèêëîâ. Êîëè÷åñòâî âñåõ òàêèõ ïåðåñòàíîâîê, ïîëó-
÷åííûõ îäíèì èç èçâåñòíûõ ìåòîäîâ, ðàññìîòðåííûõ â [1], ñîñòàâëÿåò
Card P N n n nN m� �
! ( )!1 2 � . Çäåñü n n nm1 2, , ,� — äëèíû öèêëîâ â ðàçëî-
æåíèè ïåðåñòàíîâêè íà ïðîèçâåäåíèå öèêëîâ. Ñðàâíèì êîëè÷åñòâî ïåðåñòàíîâîê,
óäîâëåòâîðÿþùèõ óñëîâèÿì çàäà÷ 1, 2, ò.å. êîëè÷åñòâî ýëåìåíòîâ êîðòåæà öèê-
ëè÷åñêèõ ïåðåñòàíîâîê TP
N
c , ñãåíåðèðîâàííûõ ïðåäëîæåííûì ìåòîäîì, ñ êîëè-
÷åñòâîì âñåâîçìîæíûõ ïåðåñòàíîâîê èç N ýëåìåíòîâ. Ñîãëàñíî (4) êîëè÷åñòâî
âñåõ ïåðåñòàíîâîê, ïðåäñòàâèìûõ â âèäå ïðîèçâåäåíèÿ m öèêëîâ äëèí
n n nm1 2, , ,� ñîîòâåòñòâåííî ðàâíî Card TP n n n
N
c
m� �
�
�( )! ( )! ( )!1 21 1 1� .
Ðàññìîòðèì îòíîøåíèå ìîùíîñòåé ýòèõ ìíîæåñòâ:
Card
Card
P
TP
N
n n n
N
N
c
m
� �
�
�
�
��
!
( )! ( )! ( )!1 21 1 1�
�
N
n n n
n n n
m
m
!
! ! !1 2
1 2
�
� .
(10)
Ïåðâûé ñîìíîæèòåëü â ïðàâîé ÷àñòè ñîîòíîøåíèÿ (10) ïðåäñòàâëÿåò ñîáîé êî-
ëè÷åñòâî ïåðåñòàíîâîê ñ ïîâòîðåíèÿìè èç m ðàçëè÷íûõ ýëåìåíòîâ, ãäå ïåðâûé ýëå-
ìåíò ïîâòîðÿåòñÿ n1 ðàç, âòîðîé — n2 ðàç, …, m -é ýëåìåíò — nm ðàç, ò.å.
� �
n n n P N n n nm m1 2 1 2� �Card ( , , , , ) . (11)
Òàêèì îáðàçîì, ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå. Êîëè÷åñòâî âñåõ ïåðåñòàíîâîê N ðàçëè÷íûõ ýëåìåíòîâ, ïðåä-
ñòàâèìûõ â âèäå ïðîèçâåäåíèÿ m öèêëîâ äëèí n n nm1 2, , ,� ñîîòâåòñòâåííî, â � ðàç
ìåíüøå êîëè÷åñòâà âñåõ ïåðåñòàíîâîê èç N ðàçëè÷íûõ ýëåìåíòîâ, ãäå � îïðåäåëÿ-
åòñÿ ñîîòíîøåíèåì (11).
ÇÀÊËÞ×ÅÍÈÅ
Ïðåäëîæåííûé â ðàáîòå ïîäõîä ê ãåíåðàöèè ïåðåñòàíîâîê, ñîäåðæàùèõ öèêëû,
ÿâëÿåòñÿ â äîñòàòî÷íîé ñòåïåíè óíèâåðñàëüíûì. Èñïîëüçóÿ åãî, ìîæíî ãåíåðèðî-
âàòü ïåðåñòàíîâêè, ñîäåðæàùèå öèêëû, ñ ó÷åòîì áîëüøîãî íàáîðà òðåáîâàíèé ê
êîëè÷åñòâó öèêëîâ, èõ äëèíå è ò.ä.
104 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
Ñëåäóåò îòìåòèòü, ÷òî ðàññìîòðåííûå â ñòàòüå ïîäõîäû ê ãåíåðàöèè ïåðåñòà-
íîâîê, ñîäåðæàùèõ öèêëû, èìåþò âûñîêóþ âû÷èñëèòåëüíóþ ñëîæíîñòü. Îäíàêî
ïðèìåíåíèå ïðåäëîæåííûõ ìåòîäîâ îïðàâäàíî ïðè íåîáõîäèìîñòè ãåíåðàöèè
ñëîæíûõ êîìáèíàòîðíûõ îáúåêòîâ â çàäà÷àõ ðàçëè÷íûõ êëàññîâ.  ýòîé ñèòóàöèè
ïðèìåíåíèå óêàçàííûõ ìåòîäîâ ïðèâåäåò ê çíà÷èòåëüíîìó ñíèæåíèþ èçáûòî÷íîñ-
òè, õàðàêòåðíîé äëÿ óíèâåðñàëüíûõ ìåòîäîâ ãåíåðàöèè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. K n u t h D . The art of computer programming, Volume 4, Fascicle 2: Generating all tuples and permuta-
tions. — Addison-Wesley, 2005. — 144 p.
2. K n u t h D . The art of computer programming, Volume 4, Fascicle 3: Generating all combinations and
partitions. — Addison-Wesley, 2005. — 160 ð.
3. K r e h e r D . L . , S t i n s o n D . R . Combinatorial algorithms: Generation enumeration and search.
— CRC Press, 1999. — 329 p.
4. B o n a M . Combinatorics of Permutations. — Chapman Hall-CRC, 2004. — 383 p.
5. R u s k e y F . Combinatorial generation, Dept. of Comput. Sci. Univ. of Victoria, Canada, 1j-CSC
425/520. — 2003 — 289 p.
6. K o r s h J . F . , L a F o l l e t t e P . S . Loopless array generation of multiset permutations // The Comp.
Journ. — 2004. — 47, N 5. — P. 612–621.
7. Ò è ì î ô å å â à Í . Ê . Îá îñîáåííîñòÿõ ôîðìèðîâàíèÿ è óïîðÿäî÷åíèÿ âûáîðîê // Êèáåðíåòèêà è
ñèñòåìíûé àíàëèç. — 2004. — ¹ 3. — Ñ. 179–187.
8. Ñ å ì å í î â à Í .  . , Ê î ë å ÷ ê è í à Ë . Í . Ìíîãîêðèòåðèàëüíûå çàäà÷è êîìáèíàòîðíîé
îïòèìèçàöèè íà ìíîæåñòâå ïîëèðàçìåùåíèé: ïîëèýäðàëüíûé ïîäõîä ê ðåøåíèþ // Òàì æå. — 2009.
— ¹ 3. — Ñ. 118–126.
9. Å ì å ö Î . À . , Å ì å ö Å . Ì . Ìîäèôèêàöèÿ ìåòîäà êîìáèíàòîðíîãî îòñå÷åíèÿ â çàäà÷àõ
îïòèìèçàöèè íà âåðøèííî ðàñïîëîæåííûõ ìíîæåñòâàõ // Òàì æå. — 2009. — ¹ 5. — Ñ. 129–136.
10. Ä î í å ö à . À . , Ê î ë å ÷ ê è í à Ë . Í . Ìåòîä óïîðÿäî÷åíèÿ çíà÷åíèé ëèíåéíîé ôóíêöèè íà
ìíîæåñòâå ïåðåñòàíîâîê // Òàì æå. — 2009. — ¹ 2. — Ñ. 50–61.
11. Ñ ò î ÿ í Þ . Ã . , Ã ð å á å í í è ê È . Â . Îïèñàíèå êëàññîâ êîìáèíàòîðíûõ êîíôèãóðàöèé íà îñíîâå
îòîáðàæåíèé // Äîïîâ³ä³ ÍÀÍ Óêðà¿íè. — 2008. — ¹ 10. — Ñ. 28–31.
12. Ñ ò å í ë è Ð . Ïåðå÷èñëèòåëüíàÿ êîìáèíàòîðèêà. — Ì.: Ìèð, 1990. — 440 ñ.
13. B e r g e r o n F . , L a b e l l e G . , L e r o u x P . Combinatorial species and tree-like structures. — Cam-
bridge: University Press, 1998. — 457 p.
14. H e r b e r t S . Wilf Generatingfunctionology, A K Peters, Ltd. — Massachusetts: Wellesley, 2006. —
226 p.
15. G r e b e n n i k I . V . , S t o y a n Y u . G . Enumeration and constructive tools of generating special combi-
natorial sets // Proc. 23-rd Europ. Conf. on Oper. Res. — Bonn, Germany. — 2009. — P. 207.
Ïîñòóïèëà 05.11.2009
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 105
|
| id | nasplib_isofts_kiev_ua-123456789-45650 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-29T08:16:45Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Гребенник, И.В. 2013-06-17T06:40:40Z 2013-06-17T06:40:40Z 2010 Описание и генерация перестановок, содержащих циклы / И.В. Гребенник // Кибернетика и системный анализ. — 2010. — № 6. — С. 97–105. — Бібліогр.: 15 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45650 519.85 Запропоновано загальний підхід до генерації перестановок, що містять цикли, на основі введених конструктивних засобів опису комбінаторних множин. Формулюються та розв’язуються різні задачі генерації перестановок заданого класу. Для опису перестановок, представлених у вигляді добутку заданої кількості циклів, вводиться комбінаторна множина. Для введеної множини будуються комбінаторний вид та відповідний твірний ряд. Наводяться приклади. The paper proposes a general approach to generating permutations that contain cycles, based on constructive tools introduced to describe combinatorial sets. Different generation problems for permutations of definite class are formulated and solved. A combinatorial set is introduced to define permutations represented as the multiplication of a definite number of cycles. For this set, combinatorial species and associated generating series are constructed. Examples are given. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Описание и генерация перестановок, содержащих циклы Опис та генерація перестановок, що містять цикли Description and generation of permutations containing cycles Article published earlier |
| spellingShingle | Описание и генерация перестановок, содержащих циклы Гребенник, И.В. Системный анализ |
| title | Описание и генерация перестановок, содержащих циклы |
| title_alt | Опис та генерація перестановок, що містять цикли Description and generation of permutations containing cycles |
| title_full | Описание и генерация перестановок, содержащих циклы |
| title_fullStr | Описание и генерация перестановок, содержащих циклы |
| title_full_unstemmed | Описание и генерация перестановок, содержащих циклы |
| title_short | Описание и генерация перестановок, содержащих циклы |
| title_sort | описание и генерация перестановок, содержащих циклы |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45650 |
| work_keys_str_mv | AT grebennikiv opisanieigeneraciâperestanovoksoderžaŝihcikly AT grebennikiv opistageneracíâperestanovokŝomístâtʹcikli AT grebennikiv descriptionandgenerationofpermutationscontainingcycles |