Лексикографічний порядок — відношення лінійного порядку на множині кортежів ; — упорядкований алфавіт. Свою назву лексикографічний порядок отримав по аналогії з сортуванням по алфавіту в словнику.
Нехай у списку букв алфавіту порядок букв фіксований, тобто завжди один і той самий. Тоді цей список визначає повне впорядкування букв, які назвемо відношення передування і позначимо (, якщо передує у списку букв). На основі відношення передування букв — будуємо відношення передування слів, визначене наступним чином: Нехай дано слова та , тоді , якщо виконується перший або другий пункт.
- та (β, g, d — деякі слова, можливо, порожні, та — букви)
- , де β — непорожнє слово.
Це відношення задає повне впорядкування множин всіх кінцевих слів у алфавіті «», яке називається лексикографічним упорядкуванням слів.
Приклади
- Приклад лексикографічного упорядкування є упорядкування слів в словнику. Вважається, що букви можна порівнювати, порівнюючи їх номери в абетці. Тоді лексикографічний порядок — це, наприклад, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ, або А < АА < ААА < ААБ < ААВ < АБ < Б < … < ЯЯЯ.
Ліс <= літо (випадок — 1 визначення: β = лі, с <= т, g — пусто; d = о), тому слово «ліс» розташоване в словнику раніше слова «літо», ліс <= лісовик (випадок — 2 визначення: β = овик).
- Якщо розглянути числа в позиційних системах числення (наприклад, у двійковій або десятковій системі) як слова в алфавіті цифр, то їх лексикографічний порядок збігається із звичайним, якщо всі числа, які порівнюємо мають однакове число розрядів. У загальному випадку ці два види упорядкування можуть не збігатися: наприклад, 10<1073 і 20<1073, але 10 <= 1073, а 20 =>1073. Для того щоб вони збігалися необхідно вирівняти число розрядів у всіх чисел, які порівнюємо, дописуючи зліва нулі. У наведеному прикладі отримаємо 0020 <= 1073. Таке вирівнювання автоматично відбувається при запису цілих чисел в ЕОМ. Послідовність чисел у будь-якій системі числення, записаних у фіксованій розрядній сітці (000, 001, 002, 003, 004, 005, …, 999).
- Лексикографічне упорядкування для дат виду 06.09.99 (шосте вересня 1999 року) не збігається з природним упорядкуванням дат від ранніх до пізніх, наприклад 06.09.99 лексикографічно «більше» п'ятого числа будь-якого місяця другого року. Щоб зростання дат збігалося з лексикографічним упорядкуванням, цифри потрібно виставити в такому порядку рік, потім місяць, потім день: 99.09.06. Цей аспект врахований в форматі ISO 8601.
Див. також
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Leksikografichnij poryadok vidnoshennya linijnogo poryadku na mnozhini kortezhiv S displaystyle Sigma S displaystyle Sigma uporyadkovanij alfavit Svoyu nazvu leksikografichnij poryadok otrimav po analogiyi z sortuvannyam po alfavitu v slovniku Nehaj u spisku bukv alfavitu S displaystyle Sigma poryadok bukv fiksovanij tobto zavzhdi odin i toj samij Todi cej spisok viznachaye povne vporyadkuvannya bukv yaki nazvemo vidnoshennya pereduvannya i poznachimo lt displaystyle lt a i lt a j displaystyle a i lt a j yaksho a i displaystyle a i pereduye a j displaystyle a j u spisku bukv Na osnovi vidnoshennya pereduvannya bukv buduyemo vidnoshennya pereduvannya sliv viznachene nastupnim chinom Nehaj dano slova a 1 a 11 a 1 m displaystyle a 1 a 11 a 1m ta a 2 a 21 a 2 m displaystyle a 2 a 21 a 2m todi a 1 lt a 2 displaystyle a 1 lt a 2 yaksho vikonuyetsya pershij abo drugij punkt a 1 b a i g a 2 b a j d displaystyle a 1 beta a i g a 2 beta a j d ta a i lt a j displaystyle a i lt a j b g d deyaki slova mozhlivo porozhni a i displaystyle a i ta a j displaystyle a j bukvi a 2 a 1 b displaystyle a 2 a 1 beta de b neporozhnye slovo Ce vidnoshennya zadaye povne vporyadkuvannya mnozhin vsih kincevih sliv u alfaviti S displaystyle Sigma yake nazivayetsya leksikografichnim uporyadkuvannyam sliv PrikladiPriklad leksikografichnogo uporyadkuvannya ye uporyadkuvannya sliv v slovniku Vvazhayetsya sho bukvi mozhna porivnyuvati porivnyuyuchi yih nomeri v abetci Todi leksikografichnij poryadok ce napriklad AAA AAB AAV AAG YaYaYa abo A lt AA lt AAA lt AAB lt AAV lt AB lt B lt lt YaYaYa Lis lt lito vipadok 1 viznachennya b li s lt t g pusto d o tomu slovo lis roztashovane v slovniku ranishe slova lito lis lt lisovik vipadok 2 viznachennya b ovik Yaksho rozglyanuti chisla v pozicijnih sistemah chislennya napriklad u dvijkovij abo desyatkovij sistemi yak slova v alfaviti cifr to yih leksikografichnij poryadok zbigayetsya iz zvichajnim yaksho vsi chisla yaki porivnyuyemo mayut odnakove chislo rozryadiv U zagalnomu vipadku ci dva vidi uporyadkuvannya mozhut ne zbigatisya napriklad 10 lt 1073 i 20 lt 1073 ale 10 lt 1073 a 20 gt 1073 Dlya togo shob voni zbigalisya neobhidno virivnyati chislo rozryadiv u vsih chisel yaki porivnyuyemo dopisuyuchi zliva nuli U navedenomu prikladi otrimayemo 0020 lt 1073 Take virivnyuvannya avtomatichno vidbuvayetsya pri zapisu cilih chisel v EOM Poslidovnist chisel u bud yakij sistemi chislennya zapisanih u fiksovanij rozryadnij sitci 000 001 002 003 004 005 999 Leksikografichne uporyadkuvannya dlya dat vidu 06 09 99 shoste veresnya 1999 roku ne zbigayetsya z prirodnim uporyadkuvannyam dat vid rannih do piznih napriklad 06 09 99 leksikografichno bilshe p yatogo chisla bud yakogo misyacya drugogo roku Shob zrostannya dat zbigalosya z leksikografichnim uporyadkuvannyam cifri potribno vistaviti v takomu poryadku rik potim misyac potim den 99 09 06 Cej aspekt vrahovanij v formati ISO 8601 Div takozhLinijno vporyadkovana mnozhina Sistema chislennya Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi