Лексикографічно впорядковані перестановки
Представлено альтернативний спосіб запису перестановок, який названо позиційним представленням перестановки. На множині лексикографічно впорядкованих позиційних представлень перестановок, формулюються різноманітні алгебраїчні операції над перестановками у їх позиційному представленні. Доводиться, що...
Gespeichert in:
| 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 |