Лексикографічно впорядковані перестановки

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Компьютерная математика
Datum:	2016
1. Verfasser:	Чупов, С.В.
Format:	Artikel
Sprache:	Ukrainisch
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Schlagworte:	Теория и методы оптимизации
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/168428
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:	Лексикографічно впорядковані перестановки / С.В. Чупов // Компьютерная математика. — 2016. — № 2. — С. 151-161. — Бібліогр.: 4 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1860003470819459072
author	Чупов, С.В.
author_facet	Чупов, С.В.
citation_txt	Лексикографічно впорядковані перестановки / С.В. Чупов // Компьютерная математика. — 2016. — № 2. — С. 151-161. — Бібліогр.: 4 назв. — укр.
collection	DSpace DC
container_title	Компьютерная математика
description	Представлено альтернативний спосіб запису перестановок, який названо позиційним представленням перестановки. На множині лексикографічно впорядкованих позиційних представлень перестановок, формулюються різноманітні алгебраїчні операції над перестановками у їх позиційному представленні. Доводиться, що між операціями додавання та множення на множині всіх позиційних представлень перестановок n-го порядку, операціями суми та добутку по модулю n! існує ізоморфне відображення. Представлен альтернативный способ записи перестановок, который назван позиционным представлением перестановки. На множестве лексикографически упорядоченных позиционных представлений перестановок формулируются разнообразные алгебраические операции над перестановками в их позиционном представлении. Доказывается, что между операциями сложения и умножения на множестве всех позиционных представлений перестановок n-го порядка и операциями суммы и произведения по модулю n! существует изоморфное отображение. This paper presents an alternative way of writing permutations, which is called the positional representation of permutation. On the set of lexicographically ordered positional representations of permutations various algebraic operations on permutations in their positional representation are formulated. It is proved that there exists an isomorphic mapping between the operations of addition and multiplication on the set of positional representations of permutations of n-th order and the operations of sum and product modulo n!.
first_indexed	2025-12-07T16:37:31Z
format	Article
fulltext	Компьютерная математика. 2016, № 2 151 Представлено альтернативний спо- сіб запису перестановок, який названо позиційним представлен- ням перестановки. На множині лексикографічно впорядкованих по- зиційних представлень перестано- вок, формулюються різноманітні алгебраїчні операції над переста- новками у їх позиційному пред- ставленні. Доводиться, що між операціями додавання та мно- ження на множині всіх позиційних представлень перестановок n-го порядку, операціями суми та до- бутку по модулю n! існує ізомор- фне відображення.  С.В. Чупов, 2016 УДК 519.115 С.В. ЧУПОВ ЛЕКСИКОГРАФІЧНО ВПОРЯДКОВАНІ ПЕРЕСТАНОВКИ Вступ. Перестановки відіграють важливу роль у математиці та інформатиці. Зокрема в задачах комбінаторики, дискретної мате- матики, багатьох оптимізаційних задачах [1 – 3]. Так в класичній задачі про коміво- яжера та квадратичній задачі про призначен- ня перестановки є прямим об’єктом дослі- дження. Як вказувалося в [4], від вдалого вибору лексикографічного впорядкування змінних задачі залежить ефективність роботи точних та наближених методів лексикогра- фічного напрямленого перебору. Чим ближче в лексикографічному розумінні буде розта- шований оптимальний розв’язок задачі в да- ному лексикографічному порядку до лекси- кографічного екстремуму множини допусти- мих значень тим швидше він буде отрима- ний. Але кожному лексикографічному по- рядку відповідає певна перестановка індексів змінних. Тому проблема перегляду, аналізу та перетворення перестановок у процесі роз- в’язання багатьох задач, зокрема задач дис- кретної оптимізації є дуже важлива та акту- альна. Але не слід забувати, що навіть при відносно невеликій розмірності перестановки їх загальна кількість є великою. Так, напри- клад, кількість перестановок розмірності 50 представляє собою 65-и розрядне ціле десяткове число: 50! = 304140932017133780436126081660647688443 77641568960512000000000000. В роботі розглядається альтернативний спосіб представлення перестановок, який до- зволяє над впорядкованими перестановками визначати різноманітні алгебраїчні операції. С.В. ЧУПОВ Компьютерная математика. 2016, № 2152 Позиційне представлення перестановок. Якщо всі перестановки однієї ро- змірності впорядкувати за лексикографічним зростанням, тоді можна помітити певну закономірність у їх розташуванні, яка дозволяє використовувати замість звичайного представлення перестановок інший вигляд. На рис. 1 показано всі перестановки розмірності 4, які впорядковано в порядку лексикографічного зро- стання. Останній рядок на цьому рисунку містить порядкові номери або індекси перестановок у даному наборі. 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 1 1 2 2 3 3 0 0 2 2 3 3 0 0 1 1 3 3 0 0 1 1 2 2 2 3 1 3 1 2 2 3 0 3 0 2 1 3 0 3 0 1 1 2 0 2 0 1 3 2 3 1 2 1 3 2 3 0 2 0 3 1 3 0 1 0 2 1 2 0 1 0 № 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 РИС. 1. Лексикографічно впорядковані перестановки розмірності 4 Якщо скористатися цією закономірністю та узагальнити її для перестановок довільної розмірності n, тоді перестановку  можна записати так, що в резуль- таті отримаємо цілочисловий вектор p, але на відміну від звичайної перестанов- ки цей вектор буде складатися з позицій або індексів, що визначаються певним чином, яким відповідають елементи перестановки . На рис. 2 показано струк- турну схему такого перетворення. Рис. 3 містить структурну схему алгоритму для оберненого перетворення до перестановки звичайного виду. Зауважимо, що нумерація елементів у перестановках , Ord та p починається від 0. ( , )p PermutationToPosition Ord  ( , )PositionToPermutation p Ord  Input:  – перестановка, Ord – базова перестановка Input: p – позиційне представлення, Ord – базова перестановка Output: p – позиційне представлення Output:  – перестановка   1 (int i = 0; i < n - 1; i++){ ; \ ; } 0; i i i n for p Index of in Ord Ord Ord p              (int i = 0; i < n; i++){ ; \ ; } ii p i for Ord Ord Ord          РИС. 2. Алгоритм перетворення переста- новки до позиційного виду РИС. 3. Алгоритм перетворення позиційного представлення перестановки до стандартного виду Означення 1. Вектор цілих чисел  0 1 1, ,..., ,np p p p  отриманий в резуль- таті роботи алгоритму ( , )p PermutationToPosition Ord  назвемо позиційним представленням перестановки  0 1 1, ,..., .n     ЛЕКСИКОГРАФІЧНО ВПОРЯДКОВАНІ ПЕРЕСТАНОВКИ Компьютерная математика. 2016, № 2 153 Легко бачити, що довільний цілочисловий вектор  0 1 1, ,..., np p p p  у якого кожна координата  0,1,..., 1ip n i   , 0,1,..., 1i n  є позиційним представ- ленням деякої перестановки . Надалі мінімальне ціле значення, яке більше за ip позначатимемо ,ipower тобто ,ipower n i  0,1,..., 1.i n  Базова перестановка Ord в алгоритмах PermutationToPosition та PositionToPermutation визначає яким чином будуть впорядковані перестановки. При цьому впорядкований набір перестановок завжди буде починатися з базової перестановки Ord. Якщо  0,1,..., 1Ord n  – тривіальна перестановка, тоді за вищерозглянутими алгоритмами отримаємо стандартне лексикографічне впорядкування перестановок за зростанням, як це показано на рис. 1. Якщо, наприклад,  1,3,0,2 ,Ord  тоді за алгоритми PermutationToPosition та PositionToPermutation отримаємо впорядкування перестановок, яке показано на рис. 4. 1 1 1 1 1 1 3 3 3 3 3 3 0 0 0 0 0 0 2 2 2 2 2 2 3 3 0 0 2 2 1 1 0 0 2 2 1 1 3 3 2 2 1 1 3 3 0 0 0 2 3 2 3 0 0 2 1 2 1 0 3 2 1 2 1 3 3 0 1 0 1 3 2 0 2 3 0 3 2 0 2 1 0 1 2 3 2 1 3 1 0 3 0 1 3 1 № 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 РИС. 4. Впорядкування перестановок для  1,3,0,2Ord  На рис. 5 показано всі позиційні представлення перестановок отримані за алгоритмом PermutationToPosition, що відповідають перестановкам, які показані на рис. 1, якщо базова перестановка Ord є тривіальною. Той самий впорядкова- ний набір позиційних представлень отримаємо, якщо використовувати впоряд- кований набір перестановок з рис. 4. Взагалі, варто зазначити, що для довільної базової перестановки Ord та відповідного їй впорядкованого набору перестано- вок завжди має місце стандартне лексикографічне впорядкування позиційних представлень перестановок, які отримуються в результаті застосування алго- ритму PermutationToPosition. Крім того, не важко помітити, що значення остан- нього елемента в довільному позиційному представленні завжди дорівнює 0. 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 0 0 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1p 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 № 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 РИС. 5. Позиційне представлення перестановок розмірності 4 Між множиною усіх перестановок розмірності n та множиною позиційних представлень розмірності n існує взаємно однозначна відповідність. С.В. ЧУПОВ Компьютерная математика. 2016, № 2154 Теорема 1. Для довільної перестановки  0 1 1, ,..., n     та базової перестановки Ord існує одне і тільки одне позиційне представлення  0 1 1, ,..., np p p p  , що визначається алгоритмами PermutationToPosition та PositionToPermutation. Доведення. В індексованому наборі елементів будь-який елемент однознач- но визначається своїм індексом. Крім того в довільній перестановці  усі елементи різні. Тому на кожному i-му кроці алгоритму PermutationToPosition елемента перестановки i відповідає одна і тільки одна позиція ip у базовій перестановці Ord. Нехай маємо вектор  0 1 1, ,..., np p p p  , де  0ip x Z x n i     , 0,1,..., 1.i n  Покажемо, що p однозначно визначає певну перестановку  0 1 1, ,..., .n     Зауважимо, що на початку роботи алгоритму PositionToPermutation впорядкований набір Ord представляє собою довільну перестановку розмірності n. На кожному i-му кроці алгоритму 0 ip Ord  та Ord є перестановкою розмірності ,n i тому для кожного ipOrd завжди існує лише одне значення ,ip крім того  0 1 1, ,..., ,i Ord     де елементи множи- ни  0 1 1, ,..., i   складають перестановку розмірності i. Здійснивши усі n кроків за алгоритмом PositionToPermutation отримаємо перестановку  розмірності n. Алгебраїчні операції над перестановками в позиційному представленні. Виявляється, що якщо перестановки розглядати в позиційному виді, тоді з’явля- ється можливість проводити з ними різноманітні алгебраїчні дії так, що резуль- туюча перестановка завжди буде займати правильне місце серед усіх перестано- вок, що впорядковано за базовою перестановкою Ord. В наступних структурних схемах використовуються такі позначення: a mod b – остача від ділення цілого a на ціле b; a div b – цілочислове ділення цілого a на ціле b. На рис. 6 та 7 показано структурні схеми алгоритмів для відшукання суми та різниці двох позиційних представлень перестановок однієї розмірності відпо- відно. На кожному кроці k цілочислове значення power представляє собою верх- ню межу значень, яка обмежує значення kp у даній позиції ( kp power ). Цілочислове значення carry – величина переносу, яка враховується на наступ- ному кроці. Варто зазначити, якщо після завершення роботи алгоритму додавання зна- чення переносу буде відмінним від нуля, то це буде означати, що результат ма- тиме більшу розмірність ніж його операнди. При нехтуванні додатного переносу отримаємо циклічний перехід на відповідне місце з початку в множині лексико- графічно впорядкованих позиційних представлень. Так, якщо знаходити (3, 2, 0, 0) + (0, 1, 1, 0), значення переносу в кінці буде рівним 1 і при його нех- туванні в результаті отримаємо позиційне представлення (0, 0, 1, 0). ЛЕКСИКОГРАФІЧНО ВПОРЯДКОВАНІ ПЕРЕСТАНОВКИ Компьютерная математика. 2016, № 2 155 Нехай за алгоритмом AddPositions виконано операцію додавання p = 1p + 2p . На кожному кроці k алгоритму додавання значення результуючого розряду kp та розрядів операндів 1 kp і 2 kp зв’язані співвідношенням: 1 2 1k k kp p carry    ,k k kcarry power p   де 1kcarry  – значення переносу з попереднього розряду, kcarry – перенос з поточного розряду. Припустимо, що відомий результат дода- вання p та один з його доданків 2p . Виразимо 1 kp та отримаємо: 1 2 k k kp p p   1.k k kcarry power carry    Легко показати, що для довільного 0,1,..., 2k n  ,  0,1kcarry  . Зауважимо, що процес визначення 1 kp , 1,2,..., 1k n  є опера- цією знаходження різниці. Для визначення 1 kp невідоме лише значення .kcarry 1 2( , )p AddPositions p p 1 2( , )p SubPositions p p Input: 1p , 2p – позиційні представлення перестановок Input: 1p , 2p – позиційні представлення перестановок Output: позиційне представлення 1 2p p p  . Output: позиційне представлення 1 2p p p        1 1 2 0; 0; 2; 0; { ; ; ; ; } n k k k p int carry for int k n k k int summ p p int power n k p summ carry mod power carry summ carry div power                         1 1 2 0; 0; 2; 0; { ; 0; ; ( 0) 1; ; ; } n k k k p int carry for int k n k k int power n k int newCarry int pk p p carry if pk newCarry p pk newCarry power carry newCarry                             РИС. 6. Алгоритм додавання двох позиційних представлень РИС. 7. Алгоритм відшукання різниці двох позиційних представлень Але проаналізувавши можливі чотири випадки: 1) 10, 0k kcarry carry   , 1 2 k k kp p p  ; 2) 10, 1k kcarry carry   , 1 2 1k k kp p p   ; 3) 11, 0k kcarry carry   , 1 2 k k k kp p p power   ; 4) 11, 1k kcarry carry   , 1 2 1k k k kp p p power    С.В. ЧУПОВ Компьютерная математика. 2016, № 2156 можна зробити висновок, що запозичення робимо лише тоді ( 1kcarry  ), коли 2 1 0.k k kp p carry    Таким чином на кожному кроці k значення 1 kp обчислю- ється однозначно. Тому для відшукання значення різниці поточного розряду можна використовувати формулу 1 2 k k k k kp p p carry power    . Отже якщо p = 1p + 2 ,p тоді 1p = p – 2p або 2p = p – 1p та навпаки. Має місце теорема: Теорема 2. Для довільних двох позиційних представлень 1p та 2p сума p = 1p + 2p знайдена за алгоритмом AddPositions правильна тоді і тільки тоді, коли за алгоритмом SubPositions різниці 1p = p – 2p або 2p = p – 1p знайдені правильно. На рис. 8 та 9 показано структурні схеми порозрядного множення та ділення позиційного представлення перестановки на ціле число відповідно. Зауважимо, якщо після завершення роботи алгоритму множення carry>0, тоді результат матиме більшу розмірність, ніж його операнд 1.p 1( , )p MulPositions p multiplier 1( , )p DivPositions p divider Input: 1p – позиційне представ- лення перестановки; multiplier – цілий множник Input: 1p – позиційне представлення пере- становки; divider – натуральний дільник Output: позиційне представлення 1p multiplier p  Output: позиційне представлення 1pp divider    1 1 0; 0; 2; 0; { ; ; ; ; } n k k p int carry for int k n k k int power n k int mul multiplier p carry p mul mod power carry mul div power                              1 1 1 0; 0; 0; 1; { ; ; ; } n k k k p int carry for int k k n k int power n k p p power carry div divider carry p power carry mod divider                        РИС. 8. Алгоритм множення позиційного представлення на ціле число РИС. 9. Алгоритм ділення позиційного представлення на ціле число ЛЕКСИКОГРАФІЧНО ВПОРЯДКОВАНІ ПЕРЕСТАНОВКИ Компьютерная математика. 2016, № 2 157 Зазначимо, що якщо після завершення роботи алгоритму ділення значення переносу carry > 0, тоді ділення відбулося з остачею. В цьому разі 2 2 pp s s        . Як буде показано в наступному пункті позиційне представлення розмірності n виду: 1 = 2 0,0,...,0,1,0 n         відіграє роль одиниці. Тоді за наявності додатної остачі rem отримаємо 2 2 ˆ.pp s rem p s          Властивості лексикографічно впорядкованих позиційних представлень перестановок. Серед усіх лексикографічно впорядкованих позиційних пред- ставлень розмірності n можна виділити два представлення, які мають цілком визначені структуру та зміст. Означення 2. Позиційне представлення 0,0,...,0 n         називатимемо позицій- ним представленням нуля і позначатимемо 0. Означення 3. Позиційне представлення 2 0,0,...,0,1,0 n         будемо називати по- зиційним представленням одиниці і позначатимемо 1. Не важко помітити, наприклад з рис. 5, що це перші два позиційні пред- ставлення у лексикографічно впорядкованому наборі позиційних представлень перестановок. Легко показати, що для позиційного представлення нуль мають місце наступні властивості: 0p p  , 0p p  , 0 0d   , 0p p  , де p – довільне позиційне представлення, d – ціле число. Нехай маємо два позиційні представлення 1p та 2p , причому вони розмі- щені строго лексикографічно один за одним, іншими словами вони є сусідніми та 1p L 2.p Тоді 1 21 ,p p  2 1 1.p p  Оскільки всі позиційні представлення впорядковано лексикографічно, то для довільних двох різних позиційних представлень дуже просто визначається яке з них лексикографічно більше за інше. Але питання на скільки одне позицій- не представлення більше або менше за інше лишається відкритим. Для того щоб це визначити розпишемо процес множення позиційного представлення на число за алгоритмом з рис. 8. С.В. ЧУПОВ Компьютерная математика. 2016, № 2158 2 1 2 2 2 2 2 1 3 2 3 3 3 2 1 1 2 1 0 1 0. n n n n n n n n n k k k k k d p carry power p d p carry carry power p d p carry carry power p d p carry p                                    (1) Система (1) представляє собою порозрядне співвідношення між операндом 2 ,p результатом 1p та значеннями переносів у процесі роботи алгоритму мно- ження 2p на ціле d. В останньому рівнянні системи вважатимемо, що 0 0,carry  тобто останнім переносом при виконанні операції множення знехтуємо. Починаючи з останньо- го рівняння системи (1) поступово виразимо невідомі kcarry – значення перено- сів на кожному k-му кроці алгоритму множення. В результаті отримаємо: 1 11 1 1 2 0 01 1 k kk k k j i j i j ji j i j carry p power d p power             , 1,2,..., 1k n  . Оскільки на початку операції множення переносу не має, 1 0,ncarry   то отримаємо: 2 2 2 2 2 1 0 1 0 1 . n n n n j i j i j i j j i j d p power p power               З того, що ipower n i  , легко бачити:   2 1 1 ! n i i j power n i       та     2 2 2 1 0 0 1 ! 1 ! n n j j j j d p n j p n j           . Теорема 3. Якщо 1p та 2p позиційні представлення, причому 1p L 2p L 0 , тоді їх відношення 1 2 pd p  визначається як     2 1 0 2 2 0 1 ! 1 ! n j j n j j p n j d p n j            . Фактично, знайдене ціле значення відношення двох позиційних представ- лень визначає кількість лексикографічних інтервалів 20 ,L Lp p  що містяться у лексикографічному інтервалі 10 .L Lp p  На підставі теореми 3, легко доводяться наступні наслідки. Наслідок 1. Для довільного позиційного представлення p його порядковий номер  IndexOf p у лексикографічно впорядкованому наборі усіх позиційних представлень визначається як     2 0 1 ! n j j IndexOf p p n j      . ЛЕКСИКОГРАФІЧНО ВПОРЯДКОВАНІ ПЕРЕСТАНОВКИ Компьютерная математика. 2016, № 2 159 Наслідок 2. Для довільного невід’ємного цілого числа Index < !n , існує одне і тільки одне позиційне представлення розмірності n. Наслідок 3. Для довільного невід’ємного цілого числа d<n!, позиційного представлення p має місце: ,dp d p p   де dp – позиційне представлення з індексом d у лексикографічно впорядкованій множині позиційних представлень. Між алгебраїчними операціями над позиційним представленнями переста- новки та арифметичними операціями над їх порядковими номерами існує взаєм- но однозначна відповідність. Теорема 4. Нехай 1p та 2p позиційні представлення, m, d – натуральні числа. sump = 1 2 ,p p subp = 1 2 ,p p mulp = 1,m p divp = 1p d тоді і тільки тоді коли          1 2 1,sum subIndexOf p IndexOf p IndexOf p IndexOf p IndexOf p             2 1 11, , .mul divIndexOf p IndexOf p m IndexOf p IndexOf p IndexOf p d      Доведення. Доведення проведемо тільки для операції додавання. Для інших операцій доведення здійснюється аналогічно. Нехай sump = 1 2.p p Покажемо, що  sumIndexOf p =    1 2IndexOf p IndexOf p . Згідно алгоритму додавання на ( див. рис. 6) на k-му кроці 1 2 1 sum sum k k k k k k kp p carry p carry power p       + kcarry   n k . Звідки маємо,          2 2 2 1 2 1 0 0 0 1 ! 1 ! 1 ! n n n sum sum j j j j j j j IndexOf p p n j p p n j carry n j                      –   2 0 ! n j j carry n j     . Оскільки переноси 1ncarry  та 0carry рівні нулю, отримаємо   3 1 0 1 ! n j j carry n j          2 1 ! n j j carry n j     = 0. Отже      2 2 1 2 1 0 0 1 ! 1 ! n n j j j j j p p n j carry n j                 2 0 ! n j j carry n j      =    2 1 2 0 1 ! n j j j p p n j      =   2 1 0 1 ! n j j p n j     +   2 2 0 1 ! n j j p n j     = =    1 2IndexOf p IndexOf p . С.В. ЧУПОВ Компьютерная математика. 2016, № 2160 Нехай  sumIndexOf p =    1 2IndexOf p IndexOf p . Покажемо, що sump = 1 2p p . Помножимо ліву і праву частину рівняння на p̂ . Отримаємо   ˆsumIndexOf p p =     1 2 ˆIndexOf p IndexOf p p  . З доведення наслідку 2     1 2 ˆIndexOf p IndexOf p p  =    1 2ˆ ˆIndexOf p p IndexOf p p   . Крім того з цього ж наслідку   ˆsumIndexOf p p = sump ,  1 ˆIndexOf p p = 1p ,  2 ˆIndexOf p p = 2p . В результаті отримали, що sump = 1 2.p p Аналізуючи алгебраїчні операції з попереднього пункту можна зробити висновок, що між операціями додавання та множення на множині всіх позицій- них представлень перестановок n-го порядку та операціями суми та добутку по модулю n! існує ізоморфне відображення, яке описується при доведенні наслідків 2, 3 та теореми 4, тобто, якщо 1 2,p p – довільні позиційні пред- ставлення перестановок, тоді  1 2IndexOf p p =  1IndexOf p +  2IndexOf p та  1 2IndexOf p p =    1 2IndexOf p IndexOf p . Висновки. Отримані в роботі результати дозволяють по новому розглянути вже відомі та будувати нові алгоритми для розв’язання задач в яких явно чи не- явно використовуються перестановки. В таких алгоритмах певний напрямлений перегляд перестановок можна замінити напрямленим переглядом деякої впоряд- кованої множини цілих чисел кожне значення з яких є індексом певної переста- новки у множині перестановок впорядкованих за базовою перестановкою Ord. Крім того, використання прямих лексикографічних обмежень дозволяє будувати різноманітні розбиття впорядкованої множини перестановок, що дає можливість побудови різних схем паралельних алгоритмів. Якщо в розбитті всі підмножини відповідають лексикографічним інтервалам однакової довжини з лексикографічно впорядкованої множини позиційних представлень, тоді є можливість організувати напрямлений перебір не окремих перестановок а цілих підмножин, причому робити це можна за їх індексами. С.В. Чупов ЛЕКСИКОГРАФИЧЕСКИ УПОРЯДОЧЕННЫЕ ПЕРЕСТАНОВКИ Представлен альтернативный способ записи перестановок, который назван позиционным представлением перестановки. На множестве лексикографически упорядоченных позиционных представлений перестановок формулируются разнообразные алгебраические операции над перестановками в их позиционном представлении. Доказывается, что между операциями сложения и умножения на множестве всех позиционных представлений переста- новок n-го порядка и операциями суммы и произведения по модулю n! существует изоморф- ное отображение. ЛЕКСИКОГРАФІЧНО ВПОРЯДКОВАНІ ПЕРЕСТАНОВКИ Компьютерная математика. 2016, № 2 161 S.V. Chupov LEXICOGRAPHICALLY ORDERED PERMUTATIONS This paper presents an alternative way of writing permutations, which is called the positional representation of permutation. On the set of lexicographically ordered positional representations of permutations various algebraic operations on permutations in their positional representation are formulated. It is proved that there exists an isomorphic mapping between the operations of addition and multiplication on the set of positional representations of permutations of n-th order and the operations of sum and product modulo n!. 1. Кнут Д. Искусство программирования, том 3. Сортировка и поиск. М.: Вильямс, 2007. С. 824. 2. Андерсон Дж. Дискретная математика и комбинаторика. – М.: Вильямс, 2006. С. 960. 3. Стенли Р. Перечислительная комбинаторика. М.: Мир, 1990. С. 440. 4. Чупов С.В. Новые подходы к решению задач дискретного программирования на основе лексикографического поиска. Кибернетика и системный анализ. 2016. № 4. С. 43 – 54. Одержано 17.10.2016 Про автора: Чупов Сергій Вікторович, кандидат фізико-математичних наук, доцент кафедри системного аналізу і теорії оптимізації Ужгородського національного університету. Е-mail: sergey.chupov(at)gmail.com
id	nasplib_isofts_kiev_ua-123456789-168428
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	2616-938Х
language	Ukrainian
last_indexed	2025-12-07T16:37:31Z
publishDate	2016
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Чупов, С.В. 2020-05-01T19:56:13Z 2020-05-01T19:56:13Z 2016 Лексикографічно впорядковані перестановки / С.В. Чупов // Компьютерная математика. — 2016. — № 2. — С. 151-161. — Бібліогр.: 4 назв. — укр. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/168428 519.115 Представлено альтернативний спосіб запису перестановок, який названо позиційним представленням перестановки. На множині лексикографічно впорядкованих позиційних представлень перестановок, формулюються різноманітні алгебраїчні операції над перестановками у їх позиційному представленні. Доводиться, що між операціями додавання та множення на множині всіх позиційних представлень перестановок n-го порядку, операціями суми та добутку по модулю n! існує ізоморфне відображення. Представлен альтернативный способ записи перестановок, который назван позиционным представлением перестановки. На множестве лексикографически упорядоченных позиционных представлений перестановок формулируются разнообразные алгебраические операции над перестановками в их позиционном представлении. Доказывается, что между операциями сложения и умножения на множестве всех позиционных представлений перестановок n-го порядка и операциями суммы и произведения по модулю n! существует изоморфное отображение. This paper presents an alternative way of writing permutations, which is called the positional representation of permutation. On the set of lexicographically ordered positional representations of permutations various algebraic operations on permutations in their positional representation are formulated. It is proved that there exists an isomorphic mapping between the operations of addition and multiplication on the set of positional representations of permutations of n-th order and the operations of sum and product modulo n!. uk Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Лексикографічно впорядковані перестановки Лексикографически упорядоченные перестановки Lexicographically ordered permutations Article published earlier
spellingShingle	Лексикографічно впорядковані перестановки Чупов, С.В. Теория и методы оптимизации
title	Лексикографічно впорядковані перестановки
title_alt	Лексикографически упорядоченные перестановки Lexicographically ordered permutations
title_full	Лексикографічно впорядковані перестановки
title_fullStr	Лексикографічно впорядковані перестановки
title_full_unstemmed	Лексикографічно впорядковані перестановки
title_short	Лексикографічно впорядковані перестановки
title_sort	лексикографічно впорядковані перестановки
topic	Теория и методы оптимизации
topic_facet	Теория и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/168428
work_keys_str_mv	AT čupovsv leksikografíčnovporâdkovaníperestanovki AT čupovsv leksikografičeskiuporâdočennyeperestanovki AT čupovsv lexicographicallyorderedpermutations

Лексикографічно впорядковані перестановки

Institution

Ähnliche Einträge