Влияние некоторых транспозиций на циклическую структуру перестановок

Влияние некоторых транспозиций на циклическую структуру перестановок

Рассмотрены особенности влияния транспозиций специального вида на циклические перестановки. Доказаны утверждения о результате последовательного применения нескольких соответствующих транспозиций. Предложен алгоритм генерации циклических перестановок на основании доказанных утверждений. Проведены вы...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2015
Hauptverfasser: Гребенник, И.В., Черная, О.С.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Schriftenreihe:Кибернетика и системный анализ
Schlagworte:
Системный анализ
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/124934
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Влияние некоторых транспозиций на циклическую структуру перестановок / И.В. Гребенник, О.С. Черная // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 128-136. — Бібліогр.: 15 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-124934
record_format dspace
spelling nasplib_isofts_kiev_ua-123456789-1249342025-02-23T18:06:51Z Влияние некоторых транспозиций на циклическую структуру перестановок Вплив деяких транспозицій на циклічну структуру переставлень Influence of certain transpositions on the cyclic structure of permutations Гребенник, И.В. Черная, О.С. Системный анализ Рассмотрены особенности влияния транспозиций специального вида на циклические перестановки. Доказаны утверждения о результате последовательного применения нескольких соответствующих транспозиций. Предложен алгоритм генерации циклических перестановок на основании доказанных утверждений. Проведены вычислительные эксперименты. Розглянуто особливості впливу транспозицій спеціального типу на циклічні переставлення. Доведено твердження про результат послідовного застосування декількох відповідних транспозицій. Запропоновано алгоритм генерації циклічних переставлень на підставі доведених тверджень. Проведено обчислювальні експерименти. The paper considers the features of the influence of certain kind of transpositions on cyclic permutations. Assertions about the result of the successive application of multiple relevant transpositions are proved. An algorithm for generating cyclic permutations based on the proved statements is proposed. Computational experiments are performed. 2015 Article Влияние некоторых транспозиций на циклическую структуру перестановок / И.В. Гребенник, О.С. Черная // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 128-136. — Бібліогр.: 15 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124934 519.85 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
topic Системный анализ
Системный анализ
spellingShingle Системный анализ
Системный анализ
Гребенник, И.В.
Черная, О.С.
Влияние некоторых транспозиций на циклическую структуру перестановок
Кибернетика и системный анализ
description Рассмотрены особенности влияния транспозиций специального вида на циклические перестановки. Доказаны утверждения о результате последовательного применения нескольких соответствующих транспозиций. Предложен алгоритм генерации циклических перестановок на основании доказанных утверждений. Проведены вычислительные эксперименты.
format Article
author Гребенник, И.В.
Черная, О.С.
author_facet Гребенник, И.В.
Черная, О.С.
author_sort Гребенник, И.В.
title Влияние некоторых транспозиций на циклическую структуру перестановок
title_short Влияние некоторых транспозиций на циклическую структуру перестановок
title_full Влияние некоторых транспозиций на циклическую структуру перестановок
title_fullStr Влияние некоторых транспозиций на циклическую структуру перестановок
title_full_unstemmed Влияние некоторых транспозиций на циклическую структуру перестановок
title_sort влияние некоторых транспозиций на циклическую структуру перестановок
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2015
topic_facet Системный анализ
url https://nasplib.isofts.kiev.ua/handle/123456789/124934
citation_txt Влияние некоторых транспозиций на циклическую структуру перестановок / И.В. Гребенник, О.С. Черная // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 128-136. — Бібліогр.: 15 назв. — рос.
series Кибернетика и системный анализ
work_keys_str_mv AT grebennikiv vliânienekotoryhtranspozicijnacikličeskuûstrukturuperestanovok
AT černaâos vliânienekotoryhtranspozicijnacikličeskuûstrukturuperestanovok
AT grebennikiv vplivdeâkihtranspozicíjnaciklíčnustrukturuperestavlenʹ
AT černaâos vplivdeâkihtranspozicíjnaciklíčnustrukturuperestavlenʹ
AT grebennikiv influenceofcertaintranspositionsonthecyclicstructureofpermutations
AT černaâos influenceofcertaintranspositionsonthecyclicstructureofpermutations
first_indexed 2025-11-24T06:19:01Z
last_indexed 2025-11-24T06:19:01Z
_version_ 1849651512145346560
fulltext ÓÄÊ 519.85 È.Â. ÃÐÅÁÅÍÍÈÊ, Î.Ñ. ×ÅÐÍÀß ÂËÈßÍÈÅ ÍÅÊÎÒÎÐÛÕ ÒÐÀÍÑÏÎÇÈÖÈÉ ÍÀ ÖÈÊËÈ×ÅÑÊÓÞ ÑÒÐÓÊÒÓÐÓ ÏÅÐÅÑÒÀÍÎÂÎÊ Àííîòàöèÿ. Ðàññìîòðåíû îñîáåííîñòè âëèÿíèÿ òðàíñïîçèöèé ñïåöèàëüíîãî âèäà íà öèê- ëè÷åñêèå ïåðåñòàíîâêè. Äîêàçàíû óòâåðæäåíèÿ î ðåçóëüòàòå ïîñëåäîâàòåëüíîãî ïðèìåíå- íèÿ íåñêîëüêèõ ñîîòâåòñòâóþùèõ òðàíñïîçèöèé. Ïðåäëîæåí àëãîðèòì ãåíåðàöèè öèêëè- ÷åñêèõ ïåðåñòàíîâîê íà îñíîâàíèè äîêàçàííûõ óòâåðæäåíèé. Ïðîâåäåíû âû÷èñëèòåëüíûå ýêñïåðèìåíòû. Êëþ÷åâûå ñëîâà: ìíîæåñòâî ïåðåñòàíîâîê, ïåðåñòàíîâî÷íûé ìíîãîãðàííèê, êðèòåðèé ñìåæíîñòè, ñâîéñòâà ïåðåñòàíîâîê, òðàíñïîçèöèÿ, êîìáèíàòîðèêà. ÂÂÅÄÅÍÈÅ Ìíîæåñòâî ïåðåñòàíîâîê è åãî ñâîéñòâà èñïîëüçóþòñÿ ïðè ìàòåìàòè÷åñêîì ìîäåëèðîâàíèè è ðåøåíèè ìíîãèõ íàó÷íûõ è ïðèêëàäíûõ çàäà÷ [1–7]. Âàæ- íóþ ðîëü ïðè ýòîì èãðàåò öèêëè÷åñêàÿ ñòðóêòóðà ïåðåñòàíîâîê, â ÷àñòíîñòè, êîãäà ïåðåñòàíîâêà ñîäåðæèò îäèí öèêë [5, 8]. Èçâåñòíû ìåòîäû è àëãîðèòìû, ïîçâîëÿþùèå ïðîâîäèòü ðàçëîæåíèå ïåðåñòàíîâîê â ïðîèçâåäåíèå öèêëîâ è ãå- íåðèðîâàòü ïåðåñòàíîâêè ñ çàäàííîé öèêëè÷åñêîé ñòðóêòóðîé [8–12]. Îäèí èç ñïîñîáîâ èññëåäîâàíèÿ êîìáèíàòîðíûõ ìíîæåñòâ îñíîâàí íà èõ ïî- ãðóæåíèè â åâêëèäîâî ïðîñòðàíñòâî [3, 6, 7]. Âûïóêëàÿ îáîëî÷êà ìíîæåñòâà ïå- ðåñòàíîâîê, ïîãðóæåííîãî â åâêëèäîâî ïðîñòðàíñòâî, ïðåäñòàâëÿåò ñîáîé ïåðå- ñòàíîâî÷íûé ìíîãîãðàííèê [2]. Òàêîå ïîãðóæåíèå ïîçâîëÿåò èñïîëüçîâàòü ñðåä- ñòâà íåïðåðûâíîé ìàòåìàòèêè, â òîì ÷èñëå êîìáèíàòîðíûå ìíîãîãðàííèêè, ïðè àíàëèçå êîìáèíàòîðíûõ çàäà÷ [2, 13]. Îäíèì èç áàçîâûõ ñâîéñòâ ïåðåñòàíîâî÷- íîãî ìíîãîãðàííèêà åñòü êðèòåðèé ñìåæíîñòè åãî âåðøèí. Îñíîâîé ïîñòðîåíèÿ ïåðåñòàíîâîê â êîìáèíàòîðèêå ÿâëÿþòñÿ òðàíñïîçèöèè, êîòîðûå âûïîëíÿþòñÿ íà ìíîæåñòâå ïîðîæäàþùèõ ýëåìåíòîâ [5, 8].  íàñòîÿùåé ñòàòüå ïðîàíàëèçèðîâàíû ñâîéñòâà ïåðåñòàíîâîê ïðè âûïîëíåíèè â íèõ ðàçëè÷íîãî êîëè÷åñòâà òðàíñïîçèöèé, èññëåäîâàíà öèêëè÷åñêàÿ ñòðóêòóðà ïåðåñòàíîâîê, ïîëó- ÷åííûõ èç öèêëè÷åñêîé ïåðåñòàíîâêè â ðåçóëüòàòå ïðèìåíåíèÿ ê íåé îäíèõ è òåõ æå òðàíñïîçèöèé âî âñåõ âîçìîæíûõ ïîñëåäîâàòåëüíîñòÿõ, à òàêæå ðàññìîòðåí ñïåöè- àëüíûé êëàññ òðàíñïîçèöèé, ñ ïîìîùüþ êîòîðûõ ñòðîÿòñÿ ñìåæíûå âåðøèíû â ñî- îòâåòñòâèè ñ êðèòåðèåì ñìåæíîñòè âåðøèí ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà [2]. Öåëüþ äàííîé ðàáîòû ÿâëÿåòñÿ èññëåäîâàíèå öèêëè÷åñêîé ñòðóêòóðû è ñâîéñòâ ïåðåñòàíîâîê ïðè âûïîëíåíèè â íèõ òðàíñïîçèöèé ñïåöèàëüíîãî âèäà. ÁÀÇÎÂÛÅ ÎÏÐÅÄÅËÅÍÈß Îïðåäåëåíèå 1 [8]. Ëèíåéíîå óïîðÿäî÷åíèå ýëåìåíòîâ íåêîòîðîãî ïîðîæäàþùå- ãî ìíîæåñòâà A a a an= { }1 2, , ..., íàçûâàåòñÿ ïåðåñòàíîâêîé p p= =( , , ... , )a a an1 2 = =( ( ), ( ), ... , ( )) ( , , ... , )p p pa a a a a an i i in1 2 1 2 èëè n-ïåðåñòàíîâêîé, åñëè íåîáõî- äèìî îòìåòèòü, ÷òî îíà ñîäåðæèò n ýëåìåíòîâ. Îáîçíà÷èì Pn ìíîæåñòâî ïåðåñòàíîâîê, ïîðîæäåííîå ýëåìåíòàìè a a an1 2< < <K . Ðàññìîòðèì íåêîòîðóþ ïåðåñòàíîâêó p p p p= Î( ( ), ( ), ..., ( ))a a a Pn n1 2 , à òàêæå åå ýëåìåíò p( )a ai j= " Îi j Jn, , è çàïèøåì p p p p( ) ( ( )) ( )a a aj i i= = 2 . Îáîáùåííî ýòó ôîðìóëó ìîæíî ïðåäñòàâèòü â âèäå p p p pk j k i k ia a a- -= =1 1( ) ( ( )) ( ) " Îi j J n, , k n£ . 128 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 © È.Â. Ãðåáåííèê, Î.Ñ. ×åðíàÿ, 2015 Òàêèì îáðàçîì [5], åñëè äëÿ íåêîòîðîãî l ³ 1 èìååì p l i ia a( ) = , i JnÎ , è âñå ýëåìåíòû a a a ai i i l i, ( ), ( ), ... , ( )p p p2 1- ðàçëè÷íû, òî ïîñëåäîâàòåëüíîñòü ( , ( ), ( ), ..., ( ))a a a ai i i l ip p p2 1- íàçûâàåòñÿ öèêëîì äëèíû l. Îïðåäåëåíèå 2 [5]. Öèêëè÷åñêîé íàçûâàåòñÿ ïåðåñòàíîâêà p èç n ýëåìåíòîâ, ñîäåðæàùàÿ åäèíñòâåííûé öèêë äëèíû n, ò.å. p n i ia a( ) = " Îi Jn . Âñå òàêèå ïå- ðåñòàíîâêè áóäåì îáîçíà÷àòü pC . Îáîçíà÷èì Pn C ìíîæåñòâî öèêëè÷åñêèõ ïåðåñòàíîâîê áåç ïîâòîðåíèé èç n äåéñòâèòåëüíûõ ÷èñåë a a an1 2< < <K : a a a a= Î( , , ... , )1 2 n n CP , ãäå c Ri Î , i J nnÎ = { }1 2, , ,K [5, 8]. Ñóùåñòâóåò ìíîæåñòâî ðàçëè÷íûõ âèäîâ çàïèñè ïåðåñòàíîâîê [5, 8]. Íàïðè- ìåð, çàïèñü ïåðåñòàíîâêè p = ( ) ( ) ( ) ( )2 41 6 7 5 3 , ðàçëîæåííîé â ïðîèçâåäåíèå öèêëîâ, èìååò âèä 2 2 4 1 1 4 6 6 7 5 3 5 3 ¯ æ è ç ç ç ö ø ÷ ÷ ÷ ¯ ¯ æ è ç ç ç ö ø ÷ ÷ ÷ ¯ æ è ç ç ç ö ø ÷ ÷ ÷ ¯ ¯ ¯ 7 2 2 4 1 1 4 6 6 æ è ç ç ç ö ø ÷ ÷ ÷ = æ è ç ç ç ö ø ÷ ÷ ÷ ¯ æ è ç ç ç ¯ ö ø ÷ ÷ ÷ æ è ç ç ç b bZ ö ø ÷ ÷ ÷ ¯ æ è ç ç ç ¯ ¯ ö ø ÷ ÷ ÷ = æ è ç ö ø ÷ æ è ç ö ø ÷ æ è ç 7 5 5 3 3 7 2 2 4 1 1 4 6 6 Z Z ö ø ÷ æ è ç ö ø ÷ 7 5 3 5 3 7 , à çàïèñü öèêëè÷åñêîé ïåðåñòàíîâêè p = ® ® ® ® ®( )1 5 2 4 3 1 1 5 5 2 2 4 4 3 3 1 1 2 3 4 5 5 4 1 3 2 ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷ = ¯ ¯ ¯ ¯ ¯ æ è ç ç ç Z Z Z Z ö ø ÷ ÷ ÷ . Äàëåå áóäåì èñïîëüçîâàòü âèä ïðåäñòàâëåíèÿ ïåðåñòàíîâêè, ïðè êîòîðîì â âåðõíåé ñòðîêå óêàçàíû ïîðîæäàþùèå ýëåìåíòû â ïîðÿäêå èõ ïîÿâëåíèÿ â öèê- ëå, à â íèæíåé ñòðîêå — ýëåìåíòû p( )i , ïîëó÷åííûå â ðåçóëüòàòå îòîáðàæåíèÿ. ÏÎÃÐÓÆÅÍÈÅ Â ÅÂÊËÈÄÎÂÎ ÏÐÎÑÒÐÀÍÑÒÂÎ Îñóùåñòâèì îòîáðàæåíèå ìíîæåñòâ ïåðåñòàíîâîê Pn è öèêëè÷åñêèõ ïåðåñòà- íîâîê Pn C â àðèôìåòè÷åñêîå åâêëèäîâî ïðîñòðàíñòâî R n . Ñîãëàñíî [3, 6] äàí- íîå îòîáðàæåíèå (íàçûâàåìîå ïîãðóæåíèåì) çàäàäèì â âèäå f P R n: ® " = Îp p p p Pn( , , ... , )1 2 , x f p x x x E Rn n= = Î Ì( ) ( , , ... , )1 2 , x pi i= , i JnÎ , P P Pn n CÎ{ }, .  ðåçóëüòàòå ïîãðóæåíèÿ f êàæäîìó ìíîæåñòâó Pn , Pn C ïîñòàâèì âî âçàèì- íî-îäíîçíà÷íîå ñîîòâåòñòâèå ìíîæåñòâî E R nÌ : E f Pn n= ( ), E f Pn C n C= ( ). Ðàññìîòðèì ïåðåñòàíîâî÷íûé ìíîãîãðàííèê Pn , ïîðîæäåííûé ìíîæåñòâîì a a an1 2< < <K . Ïðè ýòîì vert Pn nE= — ìíîæåñòâî åãî âåðøèí. Òàê êàê ëþáàÿ öèêëè÷åñêàÿ ïåðåñòàíîâêà ïðèíàäëåæèò ìíîæåñòâó ïåðåñòàíîâîê Pn , p p pC a a= ( ( ), ( ), ...1 2 K , ( ))p a Pn nÎ , ñëåäîâàòåëüíî, âñå öèêëè÷åñêèå ïåðåñòà- íîâêè ÿâëÿþòñÿ âåðøèíàìè ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà Pn . Ââåäåì vert vertP Pn C nÌ — ïîäìíîæåñòâî âåðøèí ïåðåñòàíîâî÷íîãî ìíî- ãîãðàííèêà, ñîîòâåòñòâóþùèõ âñåâîçìîæíûì öèêëè÷åñêèì ïåðåñòàíîâêàì ñ öèê- ëîì èç n ýëåìåíòîâ, ïîðîæäåííûõ ìíîæåñòâîì a a an1 2< < <K , vert Pn C n CE= . ÑÏÅÖÈÀËÜÍÛÅ ÊËÀÑÑÛ ÒÐÀÍÑÏÎÇÈÖÈÉ Êðèòåðèé ñìåæíîñòè âåðøèí ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà îïåðèðóåò ýëå- ìåíòàìè ïîðîæäàþùåãî ìíîæåñòâà A a a an= { }1 2, , ... , è èõ ðàñïîëîæåíèåì ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 129 â ïåðåñòàíîâêå. Ñîãëàñíî êðèòåðèþ ñìåæíîñòè âåðøèíîé, ñìåæíîé ñ âåðøè- íîé u u u u u= ( , , , ... , )a a a a n1 2 3 , ñîîòâåòñòâóþùåé ïåðåñòàíîâêå p PnÎ , ÿâëÿåòñÿ âñÿêàÿ âåðøèíà, ñîîòâåòñòâóþùàÿ ïåðåñòàíîâêå pk , ïîëó÷åííîé èç p òðàíñïî- çèöèåé ýëåìåíòîâ, ðàâíûõ k è k +1 " Î -k Jn 1 [2]. Äëÿ ëþáîé âåðøèíû u Îvert Pn òðàíñïîçèöèþ ýëåìåíòîâ, ðàâíûõ i è i +1, i JnÎ -1, ïðèíàäëåæàùèõ îäíîìó öèêëó äëèíû k ñîîòâåòñòâóþùåé ïåðåñòàíîâêè p PnÎ , áóäåì íàçûâàòü òðàíñïîçèöèåé «ðàçðûâà». Ïðè ïðèìåíåíèè äàííîé òðàíñïîçèöèè ê p PnÎ ïîëó÷èòñÿ ñìåæíàÿ ñ èñõîäíîé âåðøèíà u i nÎvert P òà- êàÿ, ÷òî ñîîòâåòñòâóþùàÿ åé ïåðåñòàíîâêà p Pi nÎ ñîäåðæèò, ïî êðàéíåé ìåðå, äâà öèêëà äëèíû k1 è k2 , k k k1 2+ = . Äëÿ ëþáîé âåðøèíû u Îvert Pn òðàíñïîçèöèþ ýëåìåíòîâ, ðàâíûõ i è i +1, i JnÎ -1, ïðèíàäëåæàùèõ äâóì ðàçëè÷íûì öèêëàì äëèíû k1 è k2 ñîîòâåòñòâóþ- ùåé ïåðåñòàíîâêè p PnÎ , áóäåì íàçûâàòü òðàíñïîçèöèåé «ñîåäèíåíèÿ». Ïðè ïðèìåíåíèè äàííîé òðàíñïîçèöèè ê p PnÎ ïîëó÷èòñÿ ñìåæíàÿ ñ èñõîäíîé âåð- øèíà u i nÎvert P òàêàÿ, ÷òî ñîîòâåòñòâóþùàÿ åé ïåðåñòàíîâêà p Pi nÎ ñîäåð- æèò, ïî êðàéíåé ìåðå, îäèí öèêë äëèíû k, k k k= +1 2 . Ñëåäîâàòåëüíî, äëÿ âåðøèí u Îvert Pn îäíà òðàíñïîçèöèÿ ýëåìåíòîâ, ðàâíûõ i è i +1, i JnÎ -1, ìîæåò ÿâëÿòüñÿ ëèáî ðàçðûâîì, ëèáî ñîåäèíåíèåì öèêëîâ, êîòîðûì ýòè ýëåìåíòû ïðèíàäëåæàò.  ñëó÷àå, åñëè èñõîäíàÿ ïåðåñòàíîâêà ïðèíàäëåæèò ìíîæåñòâó öèêëè÷åñêèõ ïåðåñòàíîâîê p Pn CÎ è èìååò åäèíñòâåííûé öèêë äëèíû n, ëþáàÿ òðàíñïîçèöèÿ ýëåìåíòîâ i è i +1, i JnÎ -1, áóäåò ðàçðûâîì [13, 14]. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È ÈÑÑËÅÄÎÂÀÍÈß Ïóñòü p PnÎ — íåêîòîðàÿ ïåðåñòàíîâêà. Ðàññìîòðèì òðàíñïîçèöèè âèäà i ij j« +1, (1) ãäå i Jj nÎ -1 — íåêîòîðûé ýëåìåíò ïåðåñòàíîâêè p PnÎ , j =1 2, , ... — ïîðÿäêî- âûé íîìåð òðàíñïîçèöèè ïðè âûïîëíåíèè ïîñëåäîâàòåëüíîñòè íåñêîëüêèõ òðàíñïîçèöèé. Îñîáåííîñòüþ òðàíñïîçèöèè (1) ÿâëÿåòñÿ òî, ÷òî îíà ñîîòâåòñòâóåò êðèòåðèþ ñìåæíîñòè âåðøèí ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà. Ñ ó÷åòîì êðèòåðèÿ ñìåæíîñòè èññëåäóåì ðåçóëüòàò ïîñëåäîâàòåëüíîãî ïðèìåíåíèÿ íåñêîëüêèõ òðàíñïîçèöèé (1) ê íåêîòîðîé öèêëè÷åñêîé ïåðåñòàíîâêå. Òàêèì îáðàçîì, ïîëó÷èì íåêîòîðóþ ïîñëå- äîâàòåëüíîñòü ïîïàðíî ñìåæíûõ âåðøèí ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà. Ïðîàíàëèçèðóåì ïîëó÷åííóþ ïîñëåäîâàòåëüíîñòü ñ òî÷êè çðåíèÿ öèêëè÷åñêîé ñòðóêòóðû ïåðåñòàíîâîê, ñîîòâåòñòâóþùèõ âåðøèíàì, êîòîðûå áóäóò ïîëó÷åíû â ðåçóëü- òàòå ïðèìåíåíèÿ íåñêîëüêèõ òðàíñïîçèöèé (1) ê íåêîòîðîé öèêëè÷åñêîé ïåðåñòàíîâêå. Äàëåå èñïîëüçóåì ñëåäóþùåå îáîçíà÷åíèå: â ñëó÷àå, åñëè ê íåêîòîðîé èñ- õîäíîé ïåðåñòàíîâêå p PnÎ ïîñëåäîâàòåëüíî ïðèìåíÿåòñÿ íåñêîëüêî òðàíñïîçè- öèé (1), ðåçóëüòèðóþùóþ ïåðåñòàíîâêó p Pi i i nk1 2... Î çàïèøåì pi i ik1 2... = = « + « + « +p i i i i i ik k(( ), ( ), ... , ( ))1 1 2 21 1 1 , ãäå i i ik1 2K — ñïèñîê ïåðâûõ ýëå- ìåíòîâ òðàíñïîçèöèé â ïîðÿäêå èõ ïðèìåíåíèÿ. Íàïðèìåð, èñõîäíàÿ ïåðåñòàíîâêà p Pn CÎ èìååò âèä p = ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷ 1 4 4 6 6 2 2 5 5 8 8 3 3 7 7 1 Z Z Z Z Z Z Z . Ïðèìåíèì ê íåé îäíó òðàíñïîçèöèþ (1) òàêóþ, ÷òî i1 3= . Ñëåäîâàòåëüíî, i1 1 4+ = . Òîãäà 130 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 p i i p p( ) ( )1 1 31 3 4 1 3 3 7 7 1 4 6 « + = « = = ¯ æ è ç ç ç ¯ ¯ ö ø ÷ ÷ ÷ ¯ æ è ç ç ç Z Z Z Z Z Z 6 2 2 5 5 8 8 4 ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷ . Ïðèìåíèì åùå îäíó òðàíñïîçèöèþ (1) ñ óñëîâèåì i2 7= , i2 1 8+ = . Òîãäà p i i i i p p(( ), ( )) (( ), ( ))1 1 2 2 371 1 3 4 7 8« + « + = « « = = = ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷ 1 3 3 8 8 4 4 6 6 2 2 5 5 7 7 1 Z Z Z Z Z Z Z . ÂËÈßÍÈÅ ÄÂÓÕ ÒÐÀÍÑÏÎÇÈÖÈÉ ÍÀ ÖÈÊËÈ×ÅÑÊÓÞ ÏÅÐÅÑÒÀÍÎÂÊÓ Â ðàáîòå [15] ðàññìîòðåíû âîïðîñû î âîçäåéñòâèè òðàíñïîçèöèé (1) íà öèêëè- ÷åñêèå ïåðåñòàíîâêè.  ÷àñòíîñòè äîêàçàíî, ÷òî åñëè ê íåêîòîðîé ïåðåñòàíîâêå p Pn CÎ ïðèìåíèòü òàêèå äâå òðàíñïîçèöèè (1), ÷òî i i1 2¹ , i i1 2 1¹ + " Î -i i Jn1 2 1, , òî ðåçóëüòèðóþùàÿ ïåðåñòàíîâêà p p Pi i i i n1 2 2 1 = Î áóäåò òîãäà öèêëè÷åñêîé, êîã- äà â èñõîäíîé ïåðåñòàíîâêå p Pn CÎ â öèêëå ýëåìåíòû i1, i1 1+ , i2 , i Jn2 1+ Î , ðàñïîëîæåíû â ïîðÿäêå, ñîîòâåòñòâóþùåì îäíîìó èç òèïîâ: — òèï I x i i i i i i i a b c ¯ æ è ç ç ç ¯ ¯ + + ¯ + ö ø ÷ ÷ ÷ 1 1 2 2 1 1 21 1 1 Z Z Z p p p( ) ( ) ( ) ÷ , a b c n, , , ,Î -{ }0 2K ; — òèï II x i i i i i i i a b c ¯ æ è ç ç ç ¯ + + ¯ + + ¯ ö ø ÷ 1 1 2 2 1 1 21 1 1 1 Z Z Z p p p( ) ( ) ( ) ÷ ÷ ÷ , a b c n, , , ,Î -{ }0 2K . Ðàññìîòðèì âëèÿíèå òðàíñïîçèöèé i i1 1 1« + è i i1 11 2+ « + íà ïðîèçâîëü- íóþ öèêëè÷åñêóþ ïåðåñòàíîâêó p Pn CÎ . Óòâåðæäåíèå 1. Åñëè â ïðîèçâîëüíîé öèêëè÷åñêîé ïåðåñòàíîâêå p Pn CÎ ïî- ñëåäîâàòåëüíî âûïîëíèòü òàêèå äâå òðàíñïîçèöèè (1), ÷òî i i1 21+ = " Î -i Jn1 2 , âî âñåõ âîçìîæíûõ ïîñëåäîâàòåëüíîñòÿõ, òî èç ïîëó÷åííûõ â ðåçóëüòàòå äâóõ ðàç- ëè÷íûõ ïåðåñòàíîâîê p pi i i i1 2 2 1 ¹ òîëüêî îäíà áóäåò öèêëè÷åñêîé. Äîêàçàòåëüñòâî. Ïðè ñîâåðøåíèè äâóõ òàêèõ òðàíñïîçèöèé (1), ÷òî i i1 21+ = " Î -i i Jn1 2 1, , ïðîèñõîäèò ëèáî òðàíñïîçèöèÿ ýëåìåíòîâ i i1 1 1« + , à çà- òåì òðàíñïîçèöèÿ i i1 11 2+ « + , ëèáî òðàíñïîçèöèÿ i i1 11 2+ « + è ïîñëå íåå òðàíñïîçèöèÿ i i1 1 1« + . Ðàññìîòðèì ïîñëåäîâàòåëüíîñòè èíäåêñîâ, îáðàçîâàííûå ýëåìåíòàìè i1, i1 1+ , i1 2+ â ëþáîé ïåðåñòàíîâêå p Pn CÎ . Íåîáõîäèìî íàéòè ïîñëåäîâàòåëüíîñòü èí- äåêñîâ ñ ìèíèìàëüíûì ÷èñëîì ýëåìåíòîâ, ñîåäèíÿþùóþ ýëåìåíò i ñ îäíèì èç ýëå- ìåíòîâ i1 1+ , i1 2+ . Òàê êàê íà÷àëüíûé ýëåìåíò i1 â äàííîì ñëó÷àå åäèíñòâåííûé, îáîçíà÷èì åãî i, à ¢ Î + +i i i{ }1 11 2, — ýëåìåíò, äëÿ êîòîðîãî âûïîëíÿåòñÿ p p pl k mi i l k m n i i i i( ) , min , | ( ) , ( )= ¢ = < = + = +{ }1 11 2 , à òàêæå i i i' ' Î + +{ }1 11 2, , i i' ' '¹ , — ýëåìåíò, äëÿ êîòîðîãî p p p ps s l k mi i i i s k m n i i i( ) ( ) , max , | ( ) , ( )= Û = = < = +-' ' ' ' ' { 1 = +i 2} . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 131 Èñïîëüçîâàâ ââåäåííûå îáîçíà÷åíèÿ, ïðåäñòàâèì ñâÿçè ìåæäó ýëåìåíòàìè i1, i1 1+ , i1 2+ p x i i i i i l s l = ¯ æ è ç ç ç ¯ ¯ ö ø ÷ ÷ ÷ ÷ - Z Z p p( ) ( ) ' ' ' ' . (2) Ðàññìîòðèì âàðèàíò, ïðè êîòîðîì ñîâåðøàåòñÿ òðàíñïîçèöèÿ i i1 11 2+ « + , à çàòåì i i1 1 1« + . Òàê êàê íåèçâåñòíî, êàêîå èç îáîçíà÷åíèé, i' èëè i' ' , ñîîòâåòñòâóåò i1 1+ , áóäåì ó÷èòûâàòü îáå âîçìîæíîñòè. Èñõîäíàÿ ïåðåñòàíîâêà èìååò âèä (2). Ïðîâåäåì òðàíñïîçèöèþ ýëåìåíòîâ i' è i' ' : p x i i i i i p i i l s l i i = ¯ æ è ç ç ç ¯ ¯ ö ø ÷ ÷ ÷ ÷ Þ « - « Z Z p p( ) ( ) ( ' ' ' ' 1 2 1 2 1 ) ( ) ( ) = = ¯ æ è ç ç ç ¯ ö ø ÷ ÷ ÷ ÷ - p x i i i i i i l s l Z p p ' ' ' ' b . Ïðåäïîëîæèì, ÷òî i i' = +1 1, è ïðîâåäåì òðàíñïîçèöèþ ýëåìåíòîâ i è i': p x i i i i i p ii l s l i i i1 1 1 = ¯ æ è ç ç ç ¯ ¯ ö ø ÷ ÷ ÷ ÷ Þ « - « Z p p( ) ( ) ( ' ' ' ' i p x i i i i i i i s l l 1 1 ) ( ) ( ) = = ¯ æ è ç ç ç ¯ ¯ ö ø ÷ ÷ ÷ ÷ - ' ' ' ' Z Z p p , à òàêæå ïðåäïîëîæèì, ÷òî i i' ' = +1 1, è òîæå ïðîâåäåì òðàíñïîçèöèþ ýëåìåí- òîâ i è i' ' : p x i i i i i p ii l s l i i i1 2 1 = ¯ æ è ç ç ç ¯ ö ø ÷ ÷ ÷ ÷ Þ « - « Z p p( ) ( ) ( ' ' ' ' b i p x i i i i i i i l s l 1 1 ) ( ) ( ) = = ¯ æ è ç ç ç ç ö ø ÷ ÷ ÷ ÷ -p p ' ' ' ' b b . Ðàññìîòðèì âàðèàíò, ïðè êîòîðîì ñîâåðøàåòñÿ òðàíñïîçèöèÿ i i1 1 1« + , à çàòåì i i1 11 2+ « + . Òàê êàê íåèçâåñòíî, i' èëè i' ' ðàâíî i1 1+ , áóäåì ó÷èòûâàòü îáå âîçìîæíîñòè. Èñõîäíàÿ ïåðåñòàíîâêà èìååò âèä (2). Èñõîäÿ èç ïðåäïîëîæåíèÿ i i' = +1 1, ïðîâåäåì òðàíñïîçèöèþ ýëåìåíòîâ i è i' : p x i i i i i p i i l s l i i = ¯ æ è ç ç ç ¯ ¯ ö ø ÷ ÷ ÷ ÷ Þ « - « Z Z p p( ) ( ) ( ) ' ' ' ' ' ' = = ¯ æ è ç ç ç ¯ ö ø ÷ ÷ ÷ ÷ - p x i i i i i i s l l ' ' ' ' Z p p( ) ( ) b . Òåïåðü ïðîâåäåì òðàíñïîçèöèþ ýëåìåíòîâ i i' = +1 1 è i i' ' = +1 2: p x i i i i i p ii s l l i i i= ¯ æ è ç ç ç ¯ ö ø ÷ ÷ ÷ ÷ Þ - « ' ' ' ' ' ' '' Z p p( ) ( ) (b « = = æ è ç ç ç ç ö ø ÷ ÷ ÷ ÷ - i p x i i i i i ii s l l ' ' ' ' ' ' ') ( ) ( )p p b b b . Åñëè i i' ' = +1 1, òî ïðîâåäåì òðàíñïîçèöèþ ýëåìåíòîâ i è i' ' : p x i i i i i p i i l s l i i = ¯ æ è ç ç ç ¯ ¯ ö ø ÷ ÷ ÷ ÷ Þ « - « Z Z p p( ) ( ) ( ' ' '' ' '' ' '' ' ' ) ( ) ( ) = = ¯ ¯ æ è ç ç ç ç ö ø ÷ ÷ ÷ ÷ - p x i i i i i i l s lp p Z ^ b . 132 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 Òåïåðü ïðîâåäåì òðàíñïîçèöèþ ýëåìåíòîâ i i' ' = +1 1 è i i' = +1 2: p x i i i i i p ii l s l i i = æ è ç ç ç ¯ ö ø ÷ ÷ ÷ ÷ Þ - « b b '' ' ' ' ' '' p p( ) ( ) (Z ^ « = = æ è ç ç ç ö ø ÷ ÷ ÷÷ - ¯ ¯i p x i ii s l i i i '' ' ' ' i l '' ) ( ) ( ) bZ Z p p . Òàêèì îáðàçîì, äîêàçàíî, ÷òî â êàêîé áû ïîñëåäîâàòåëüíîñòè ýëåìåíòû i i i1 1 11 2, ,+ + íè âñòðå÷àëèñü â ïåðåñòàíîâêå p Pn CÎ , ñóùåñòâóåò åäèíñòâåííûé ñïîñîá âûïîëíèòü äâå òðàíñïîçèöèè òàê, ÷òîáû ðåçóëüòèðóþùàÿ ïåðåñòàíîâêà áûëà öèêëè÷åñêîé. ÂËÈßÍÈÅ ÒÐÅÕ ÒÐÀÍÑÏÎÇÈÖÈÉ ÍÀ ÖÈÊËÈ×ÅÑÊÓÞ ÏÅÐÅÑÒÀÍÎÂÊÓ Óòâåðæäåíèå 2. Åñëè â ïðîèçâîëüíîé öèêëè÷åñêîé ïåðåñòàíîâêå p Pn CÎ ïîñëå- äîâàòåëüíî ñîâåðøèòü òðè òðàíñïîçèöèè (1) ñ èñïîëüçîâàíèåì ëþáûõ ïîðîæäà- þùèõ ýëåìåíòîâ, òî âñå ïîëó÷åííûå â ðåçóëüòàòå ïåðåñòàíîâêè íåçàâèñèìî îò ïîñëåäîâàòåëüíîñòè âûïîëíåíèÿ òðàíñïîçèöèé íå áóäóò öèêëè÷åñêèìè. Äîêàçàòåëüñòâî. Îõàðàêòåðèçóåì òðè òðàíñïîçèöèè â òåðìèíàõ ðàçðûâîâ è ñîåäèíåíèé. Òàê êàê èñõîäíàÿ ïåðåñòàíîâêà èìååò åäèíñòâåííûé öèêë äëè- íû n, ïåðâàÿ òðàíñïîçèöèÿ ìîæåò ÿâëÿòüñÿ òîëüêî ðàçðûâîì ¹ 1 [14, 15]. Ïðåä- ñòàâèì ñëåäóþùèå äâå òðàíñïîçèöèè, ðàññìàòðèâàÿ îòäåëüíî âñå ñëó÷àè (â êàæ- äîì èç íèõ ïîñëå òðàíñïîçèöèè ðàçðûâà ¹ 1 èìååì â êà÷åñòâå èñõîäíîé ïåðå- ñòàíîâêó ñ äâóìÿ öèêëàìè): — ðàçðûâ ¹ 2, ðàçðûâ ¹ 3: ðàçðûâ ¹ 2 ðàçðûâàåò îäèí èç öèêëîâ íà äâà, â èòîãå èìååì òðè öèêëà, ðàçðûâ ¹ 3 ðàçðûâàåò îäèí èç öèêëîâ íà äâà, â ðåçóëü- òàòå ïîëó÷àåòñÿ ïåðåñòàíîâêà p P Pn n CÎ \ , ñîñòîÿùàÿ èç ÷åòûðåõ öèêëîâ; — ðàçðûâ ¹ 2, ñîåäèíåíèå ¹ 1: ðàçðûâ ¹ 2 ðàçðûâàåò îäèí èç öèêëîâ íà äâà, ïîëó÷àåòñÿ òðè öèêëà, ñîåäèíåíèå ¹ 1 îáúåäèíÿåò äâà èç òðåõ èìåþùèõñÿ öèêëîâ, â ðåçóëüòàòå èìååì ïåðåñòàíîâêó p P Pn n CÎ \ , ñîñòîÿùóþ èç äâóõ öèêëîâ; — ñîåäèíåíèå ¹ 1, ðàçðûâ ¹ 2: ñîåäèíåíèå ¹ 1 îáúåäèíÿåò äâà öèêëà, èç êîòîðûõ ñîñòîèò ïåðåñòàíîâêà, îáðàçóÿ öèêëè÷åñêóþ ïåðåñòàíîâêó, ïîñëå ýòîãî ðàçðûâ ¹ 2 ðàçðûâàåò öèêëè÷åñêóþ ïåðåñòàíîâêó íà äâà ðàçëè÷íûõ öèêëà, â èòîãå ïîëó÷àåòñÿ ïåðåñòàíîâêà p P Pn n CÎ \ , ñîñòîÿùàÿ èç äâóõ öèêëîâ; — ñîåäèíåíèå ¹ 1, ñîåäèíåíèå ¹ 2: ñîåäèíåíèå ¹ 1 îáúåäèíÿåò äâà öèêëà, èç êîòîðûõ ñîñòîèò ïåðåñòàíîâêà, îáðàçóÿ öèêëè÷åñêóþ ïåðåñòàíîâêó, ïîñëå ýòîãî òðåòüÿ òðàíñïîçèöèÿ íå ìîæåò ÿâëÿòüñÿ ñîåäèíåíèåì ¹ 2, òàê êàê èçâåñòíî [14, 15], ÷òî ëþáàÿ òðàíñïîçèöèÿ â öèêëè÷åñêîé ïåðåñòàíîâêå åñòü òðàíñïîçèöèÿ ðàçðûâà. Èòàê, ðàññìîòðåíû âñå âàðèàíòû äëÿ òðåõ ïîñëåäîâàòåëüíûõ òðàíñïîçèöèé è âî âñåõ ñëó÷àÿõ êîíå÷íàÿ ïåðåñòàíîâêà p P Pn n CÎ \ , ÷òî è òðåáîâàëîñü äîêàçàòü. ÃÅÍÅÐÀÖÈß ÍÅÊÎÒÎÐÛÕ ÖÈÊËÈ×ÅÑÊÈÕ ÏÅÐÅÑÒÀÍÎÂÎÊ Ñ ÏÎÌÎÙÜÞ ÄÂÓÕ ÒÐÀÍÑÏÎÇÈÖÈÉ Ðàññìîòðèì çàäà÷ó: äëÿ íåêîòîðîé èñõîäíîé öèêëè÷åñêîé ïåðåñòàíîâêè p Pn CÎ íåîáõîäèìî ñîâåðøèòü ãåíåðàöèþ ðàçëè÷íûõ öèêëè÷åñêèõ ïåðåñòàíîâîê, ïî- ñëåäîâàòåëüíî ïðèìåíÿÿ äâå òðàíñïîçèöèè (1), ñ ó÷åòîì âñåõ âîçìîæíûõ âàðè- àíîâ ðàñïðåäåëåíèÿ ýëåìåíòîâ â òðàíñïîçèöèÿõ. Ðåøèòü äàííóþ çàäà÷ó ìîæíî íà îñíîâàíèè äîêàçàííûõ óòâåðæäåíèé. Äëÿ ýòîãî ðàññìîòðèì âñå òàêèå ïàðû ýëåìåíòîâ i j, , ÷òî i nÎ -{ }3 1, ,K , j iÎ -{ }1 2, ,K . Ýòî ïîçâîëèò èñêëþ÷èòü èç ðàññìîòðåíèÿ ñëó÷àè ðàâåíñòâà ýëå- ìåíòîâ â òðàíñïîçèöèÿõ è èçáåæàòü èçáûòî÷íîñòè èññëåäîâàíèÿ ïåðåñòàíîâêè, ò.å. åñëè èçâåñòåí òèï ïåðåñòàíîâêè äëÿ ïàðû i j, , òî ïàðà j i, ðàññìàòðèâàòüñÿ íå áóäåò. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 133 Ïîñëå èññëåäîâàíèÿ âñåõ íàáîðîâ ýëåìåíòîâ i j, , i nÎ -{ }3 1, ,K , j iÎ -{ }1 2, ,K , ìîæíî îïðåäåëèòü êîëè÷åñòâî ðàçëè÷íûõ ïåðåñòàíîâîê, ðàâíîå ÷èñëó ïàð ýëåìåíòîâ, äëÿ êîòîðûõòèï ïåðåñòàíîâêè I èëè II, ïëþñ n -2 óíèêàëüíûõ ïåðåñòàíîâîê, ïîëó÷åí- íûõ èç èñõîäíîé ïóòåì äâóõ òðàíñïîçèöèé â ñîîòâåòñòâèè ñ óòâåðæäåíèåì 1. Ïðèâåäåì àëãîðèòì ãåíåðàöè. Øàã 1. Âûïîëíÿåòñÿ âíåøíèé öèêë ñî ñ÷åò÷èêîì i n= -3 1, ,K è âëîæåííûé öèêë ñî ñ÷åò÷èêîì j i= -1 2, ,K . Ïðè êàæäîì ïîâòîðåíèè öèêëà àíàëèçèðóåòñÿ ñîîòâåòñòâóþùàÿ ïàðà i j, äëÿ íàõîæäåíèÿ ïàð ýëåìåíòîâ â ïåðåñòàíîâêàõ òèïà I è II. Ïðè îáíàðóæåíèè ïàðû ýëåìåíòîâ ñîîòâåòñòâóþùåãî òèïà ïåðåñòàíîâêè ïðçîâîäèòñÿ ãåíåðàöèÿ ïåðåñòàíîâêè ñ ïîìîùüþ äâóõ òðàíñïîçèöèé: i i« +1è j j« +1, è ïîëó÷åííàÿ ïåðåñòàíîâêà çàïèñûâàåòñÿ â ìàññèâ ðåçóëüòàòîâ. Øàã 2. Âûïîëíÿåòñÿ îäèí öèêë ñî ñ÷åò÷èêîì i n= -1 1, ,K , j i= +1. Äëÿ êàæ- äîé ïàðû i j, ïðîâîäèòñÿ ãåíåðàöèÿ äâóõ ïåðåñòàíîâîê ïóòåì ïðèìåíåíèÿ òðàíñ- ïîçèöèé i i« +1 è j j« +1 âî âñåõ âîçìîæíûõ ïîñëåäîâàòåëüíîñòÿõ. Ïîëó÷åí- íûå ïåðåñòàíîâêè çàïèñûâàþòñÿ âî âðåìåííûé ìàññèâ, èç íèõ îïðåäåëÿåòñÿ öèê- ëè÷åñêàÿ è çàïèñûâàåòñÿ â ìàññèâ ðåçóëüòàòîâ. Âðåìåííûé ìàññèâ îáíóëÿåòñÿ. ÎÖÅÍÊÀ ÂÛ×ÈÑËÈÒÅËÜÍÎÉ ÑËÎÆÍÎÑÒÈ ÀËÃÎÐÈÒÌÀ ÃÅÍÅÐÀÖÈÈ Äëÿ îöåíêè ñëîæíîñòè àëãîðèòìà íåîáõîäèìî ïðîàíàëèçèðîâàòü âñå ïàðû ýëå- ìåíòîâ i j, , i nÎ -{ }3 1, ,K , j iÎ -{ }1 2, ,K , è íàéòè òå èç íèõ, ðàñïîëîæåíèå êî- òîðûõ ñîîòâåòñòâóåò ïåðåñòàíîâêàì òèïîâ I è II. Âñåãî ïàð ýëåìåíòîâ ( )i i n - = - å 2 3 1 . Îáîçíà÷èì m m i i n , ( )£ - = - å 2 3 1 , êîëè÷åñòâî ïàð ýëåìåíòîâ ïåðåñòàíîâîê òèïîâ I è II. Òîãäà èòîãîâîå êîëè÷åñòâî öèêëè÷åñêèõ ïåðåñòàíîâîê, êîòîðûå ìîæíî ïî- ëó÷èòü èç èñõîäíîé ñ ïîìîùüþ äâóõ òðàíñïîçèöèé ðàâíî: ( )n -2 ïåðåñòàíîâîê, ïîëó÷åííûõ â ðåçóëüòàòå äâóõ òðàíñïîçèöèé ñ èñïîëüçîâàíèåì òðåõ ýëåìåíòîâ, ïëþñ m ïåðåñòàíîâîê, ïîëó÷åííûõ â ðåçóëüòàòå äâóõ òðàíñïîçèöèé ñ èñïîëüçîâà- íèåì ÷åòûðåõ ðàçëè÷íûõ ýëåìåíòîâ. Äëÿ òîãî ÷òîáû ñãåíåðèðîâàòü îäíó ïåðåñòàíîâêó, àëãîðèòìó íåîáõîäèìî ñîâåðøèòü äâå òðàíñïîçèöèè ñîñåäíèõ ïî çíà÷åíèþ ýëåìåíòîâ, ñëåäîâàòåëüíî, êîëè÷åñòâî äåéñòâèé àëãîðèòìà äëÿ ãåíåðàöèè âñåõ ïåðåñòàíîâîê íåîáõîäèìî óìíîæèòü íà äâà. Èòàê, êîëè÷åñòâî ýëåìåíòàðíûõ îïåðàöèé àëãîðèòìà ðàâíî 2 2(( ) )n m- + , ãäå n — ðàçìåðíîñòü çàäà÷è, m — êîëè÷åñòâî ïàð ýëåìåíòîâ, ñîîòâåòñòâóþùèõ òè- ïàì I è II. Ñëîæíîñòè àíàëèçà, ãåíåðàöèè è àëãîðèòìà ðàâíû ñîîòâåòñòâåííî O i i n ( )- æ è ç ç ö ø ÷ ÷ = - å 2 3 1 , 2 2(( ) )n m- + è O i n m i n ( ) (( ) )- æ è ç ç ö ø ÷ ÷ + - + = - å 2 2 2 3 1 . ÂÛ×ÈÑËÈÒÅËÜÍÛÉ ÝÊÑÏÅÐÈÌÅÍÒ Â êà÷åñòâå èñõîäíîé âûáåðåì öèêëè÷åñêóþ ïåðåñòàíîâêó p = æ è ç ö ø ÷ = ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ¯ ö 1 2 3 4 5 6 5 6 1 3 2 4 1 5 5 2 2 6 6 4 4 3 3 1 Z Z Z Z Z ø ÷ ÷ ÷ . Ïðîâåäåì èññëåäîâàíèå äàííîé ïåðåñòàíîâêè äëÿ ýëåìåíòîâ i j, , i nÎ -{ }3 1, ,K , j iÎ -{ }1 2, ,K . Íàéäåì âñå ïàðû ýëåìåíòîâ i j, , äëÿ êîòîðûõ òèï ïå- ðåñòàíîâîê I èëè II: i j= =4 1, òèï I; i j= =4 2, òèï II; i j= =5 1, òèï II; i j= =5 2, òèï I. 134 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 Èòàê, ÷åòûðå íàáîðà ýëåìåíòîâ ñîîòâåòñòâóþò òèïàì, ñîõðàíÿþùèì öèêëè÷- íîñòü, ñëåäîâàòåëüíî, â äàííîì ñëó÷àå m = 4. Òîãäà äëÿ èñõîäíîé ïåðåñòàíîâêè êîëè÷åñòâî ðàçëè÷íûõ ïåðåñòàíîâîê, ïîëó÷åí- íûõ â ðåçóëüòàòå äâóõ òðàíñïîçèöèé, áóäåò ( ) ( ) ( )n m n- + = - + = - + =2 2 4 6 2 4 8. Ðàññìîòðèì ïîëó÷åíèå öèêëè÷åñêèõ ïåðåñòàíîâîê èç èñõîäíîé ñ ïîìîùüþ äâóõ òðàíñïîçèöèé ýëåìåíòîâ, ñîîòâåòñòâóþùèõ òèïàì I è II.  êà÷åñòâå ïðèìå- ðà èñïîëüçóåì ïàðó ýëåìåíòîâ: i = 4, j =1. Äëÿ òðåõ äðóãèõ ïàð òðàíñïîçèöèè ïðîâîäÿòñÿ àíàëîãè÷íî ñ ïîìîùüþ ñîîòâåòñòâóþùèõ ýëåìåíòîâ: p p p= ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷ Þ « = = « 1 5 5 2 2 6 6 4 4 3 3 1 4 5 1 4 5 4Z Z Z Z Z ( ) ¯ æ è ç ç ç ¯ ¯ ö ø ÷ ÷ ÷ ¯ æ è ç ç ç ¯ ¯ ö ø ÷ ÷ ÷ Þ « 4 4 3 3 1 5 2 2 6 6 5 1 2 Z Z Z Z Þ « = = ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷«1 2 411 2 1 4 4 3 3 2 2 6 6 5 5 1 p p( ) Z Z Z Z Z . Äàëåå ðàññìîòðèì ïîëó÷åíèå ( )n -2 öèêëè÷åñêèõ ïåðåñòàíîâîê â ðåçóëüòàòå äâóõ òðàíñïîçèöèé ñ èñïîëüçîâàíèåì òðåõ ýëåìåíòîâ. Íåèçâåñòíî, êàêîé èìåííî ïîðÿäîê ïðèìåíåíèÿ òðàíñïîçèöèé ïðèâîäèò ê öèêëè÷åñêîé ïåðåñòàíîâêå, ïîý- òîìó íåîáõîäèìî ïðîâåðÿòü ïîïàðíî âñå íàáîðû ýëåìåíòîâ. Ñðàâíèì äâå ïîñëå- äîâàòåëüíîñòè òðàíñïîçèöèé: i j= =1 2, è i = 2, j =1 (äðóãèå ïàðû ñðàâíèâàþòñÿ àíàëîãè÷íî) p p p= ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷ Þ « = = « 1 5 5 2 2 6 6 4 4 3 3 1 1 2 1 1 2 1Z Z Z Z Z ( ) ¯ æ è ç ç ç ¯ ö ø ÷ ÷ ÷ ¯ æ è ç ç ç ¯ ¯ ¯ ö ø ÷ ÷ ÷ Þ « 5 5 1 2 6 6 4 4 3 3 2 2 3 Z Z Z Z Þ « = = ¯ æ è ç ç ç ¯ ö ø ÷ ÷ ÷ ¯ æ è ç ç ç ¯ ¯ ö ø «2 3 122 3 1 5 5 1 2 6 6 4 4 2 p p( ) Z Z Z ÷ ÷ ÷ æ è ç ç ç ö ø ÷ ÷ ÷ 3 3 b ; p p p= ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷ Þ « = = « 1 5 5 2 2 6 6 4 4 3 3 1 2 3 1 2 3 2Z Z Z Z Z ( ) ¯ ¯ æ è ç ç ç ¯ ö ø ÷ ÷ ÷ ¯ æ è ç ç ç ¯ ¯ ö ø ÷ ÷ ÷ Þ « 5 5 3 3 1 2 6 6 4 4 2 1 2 Z Z Z Z Þ « = = ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷«1 2 211 2 1 4 4 2 2 6 6 5 5 3 3 1 p p( ) Z Z Z Z Z . Êðîìå ïîñòðîåííûõ äâóõ öèêëè÷åñêèõ ïåðåñòàíîâîê, èç èñõîäíîé öèêëè÷åñ- êîé ïåðåñòàíîâêè àíàëîãè÷íî ïîëó÷àþòñÿ åùå øåñòü ðàçëè÷íûõ öèêëè÷åñêèõ ïåðåñòàíîâîê: p42 1 4 4 2 2 6 6 5 5 3 3 1 = ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷ Z Z Z Z Z , p51 1 6 6 4 4 3 3 2 2 5 5 1 = ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷ Z Z Z Z Z , p52 1 6 6 4 4 2 2 5 5 3 3 1 = ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷ Z Z Z Z Z , p23 1 5 5 4 4 2 2 6 6 3 3 1 = ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷ Z Z Z Z Z , ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 135 p34 1 4 4 5 5 2 2 6 6 3 3 1 = ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷ Z Z Z Z Z , p54 1 6 6 5 5 2 2 4 4 3 3 1 = ¯ æ è ç ç ç ¯ ¯ ¯ ¯ ¯ ö ø ÷ ÷ ÷ Z Z Z Z Z . ÇÀÊËÞ×ÅÍÈÅ Â ñòàòüå èññëåäîâàíî âëèÿíèå òðàíñïîçèöèé ñïåöèàëüíîãî âèäà íà öèêëè÷åñêèå ïåðåñòàíîâêè p Pn CÎ . Ïðîàíàëèçèðîâàíî âëèÿíèå ïîñëåäîâàòåëüíîãî ïðèìåíåíèÿ òðàíñïîçèöèé íà öèêëè÷åñêóþ ñòðóêòóðó ïåðåñòàíîâîê. Äîêàçàíû óòâåðæäåíèÿ î âëèÿíèè îäíîé, äâóõ è òðåõ òðàíñïîçèöèé âèäà (1) â ðàçëè÷íûõ ïîñëåäîâàòåëü- íîñòÿõ íà öèêëè÷åñêèå ïåðåñòàíîâêè. Ïðîâåäåí àíàëèç ðàçëè÷íûõ ïîñëåäîâàòåëü- íîñòåé ïðèìåíåíèÿ òðàíñïîçèöèé. Äîêàçàííûå óòâåðæäåíèÿ ëåãëè â îñíîâó ïðåä- ëîæåííîãî àëãîðèòìà ãåíåðàöèè öèêëè÷åñêèõ ïåðåñòàíîâîê ñ ïîìîùüþ äâóõ òðàíñïîçèöèé èç íåêîòîðîé öèêëè÷åñêîé ïåðåñòàíîâêè p Pn CÎ . Îöåíåíà ñëîæ- íîñòü ïîëó÷åííîãî àëãîðèòìà, ïðîâåäåíû âû÷èñëèòåëüíûå ýêñïåðèìåíòû. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. à ð å á å í í è ê È .  . , Þ ð ÷ å í ê î Ë . Þ . Óïîðÿäî÷åíèå ïåðåñòàíîâîê ïðè ðåøåíèè çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè ñ ëèíåéíîé öåëåâîé ôóíêöèåé // Ñèñòåìè îáðîáêè ³íôîðìàö³¿. — 2007. — Âèï. 8 (66). — C. 139–142. 2. Å ì å ë è ÷ å â  . À . , Ê î â à ë å â Ì . Ì . , Ê ð à â ö î â Ì . Ê . Ìíîãîãðàííèêè, ãðàôû, îïòèìè- çàöèÿ. — Ì.: Íàóêà, 1981. — 344 ñ. 3. Ñ ò î ÿ í Þ . à . , ß ê î â ë å â Ñ .  . Ìàòåìàòè÷åñêèå ìîäåëè è îïòèìèçàöèîííûå ìåòîäû ãåî- ìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ. — Êèåâ: Íàóê. äóìêà, 1986. — 268 ñ. 4. à ð å á å í í è ê È .  . , Ï à í ê ð à ò î â À .  . , × ó ã à é À . Ì . , Á à ð à í î â À .  . Óïàêîâêà n-ìåðíûõ ïàðàëëåëåïèïåäîâ ñ âîçìîæíîñòüþ èçìåíåíèÿ èõ îðòîãîíàëüíîé îðèåíòàöèè â n-ìåð- íîì ïàðàëëåëåïèïåäå // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2010. — ¹ 5. — Ñ. 122–131 5. Ñ ò å í ë è Ð . Ïåðå÷èñëèòåëüíàÿ êîìáèíàòîðèêà: Ïåð. ñ àíãë. — Ì.: Ìèð, 1990. — 440 ñ. 6. Ñ ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . Òåîð³ÿ ³ ìåòîäè åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿.. — Ê.: ²í-ò ñèñòåìíèõ äîñë³äæåíü îñâ³òè, 1993. — 188 ñ. 7. Ñ å ì å í î â à Í .  . , Ê î ë å ÷ ê è í à Ë . Í . , Í à ã î ð í à ÿ À . Í . Ïîäõîä ê ðåøåíèþ âåêòîð- íûõ çàäà÷ äèñêðåòíîé îïòèìèçàöèè íà êîìáèíàòîðíîì ìíîæåñòâå ïåðåñòàíîâîê // Êèáåðíåòè- êà è ñèñòåìíûé àíàëèç. — 2008. — ¹ 3. — Ñ. 158–172. 8. B o n a M . Combinatorics of permutations. — Boca Raton: Chapman & Hall/CRC, 2004. — 337 p. 9. K r e h e r D . L . , S t i n s o n D . R . Combinatorial algorithms: Generation enumeration and search. — Boca Raton: CRC Press, 1999. — 329 p. 10. à ð å á å í í è ê È .  . , Ë è ò â è í å í ê î À . Ñ . Ãåíåðàöèÿ êîìáèíàòîðíûõ ìíîæåñòâ ñ çàäàí- íûìè ñâîéñòâàìè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2012. — ¹ 6. — Ñ. 106–113. 11. à ð å á å í í è ê È .  . Îïèñàíèå è ãåíåðàöèÿ ïåðåñòàíîâîê, ñîäåðæàùèõ öèêëû // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2010. — ¹ 6. — Ñ. 97–105. 12. K n u t h D . The art of computer programming. Vol.  4: Fascicle 2: Generating all tuples and permutations. — Stanford: Addison-Wesley, 2005. — 144 p. 13. È ñ à ÷ å í ê î Þ . À . Ïðèìåíåíèå ïîëèýäðàëüíîãî ïîäõîäà ê çàäà÷å íà öèêëè÷åñêèõ ïåðåñòà- íîâêàõ // Ñîâðåìåííûå êîìïüþòåðíûå èíôîðìàöèîííûå òåõíîëîãèè. — Ãðîäíî: ÃðÃÓ, 2008. — Ò. 2. — Ñ. 203–206. 14. à ð å á å í í è ê È .  . , × å ð í à ÿ Î . Ñ . Öèêëè÷åñêèå ñâîéñòâà ñìåæíûõ ïåðåñòàíîâîê ðàçëè÷- íûõ ýëåìåíòîâ // Áèîíèêà èíòåëëåêòà. — 2014. — ¹ 1 (82). — Ñ. 7–11. 15. à ð å á å í í è ê È .  . , × å ð í à ÿ Î . Ñ . Òðàíñïîçèöèè êîìïîíåíò è èõ âëèÿíèå íà öèêëè÷åñ- êóþ ñòðóêòóðó ïåðåñòàíîâîê // ICAICTSEE-2014, UNWE, Sofia, Bulgaria, 2014. Ïîñòóïèëà 27.04.2015 136 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6

Ähnliche Einträge