Лексикографический порядок — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры с комбинаторными объектами)
м (rollbackEdits.php mass rollback)
 
(не показаны 23 промежуточные версии 4 участников)
Строка 1: Строка 1:
== Определение ==
 
 
{{Определение
 
{{Определение
|definition=Пусть даны две последовательности <tex> ~A = a_1 a_2 ... a_n </tex>  и <tex> ~B = b_1 b_2 ... b_m </tex>  
+
|definition=Пусть даны две последовательности <tex> ~A = a_1 a_2 \dots a_n </tex>  и <tex> ~B = b_1 b_2 \dots b_m </tex>  
Тогда последовательность <tex> ~A </tex> '''лексикографически меньше''' последовательности <tex> ~B </tex>, если выполняется одно из двух условий:
+
Тогда последовательность <tex> ~A </tex> '''лексикографически меньше''' (англ. ''lexicographically less'') последовательности <tex> ~B </tex>, если выполняется одно из двух условий:
*<tex> n < m </tex> и при этом <tex> a_i = b_i </tex> для всех <tex>i \in [1; n] </tex>,
+
*<tex> n < m </tex> и при этом <tex> a_i = b_i </tex> для всех <tex>i \in [1 .. n] </tex>,
* <tex> \mathcal {9} k\leqslant \min(n, m): a_k < b_k </tex>  и при этом <tex> \mathcal {8} j < k ~a_j = b_j </tex>.
+
* <tex> \exists k\leqslant \min(n, m): a_k < b_k </tex>  и при этом <tex> \forall j : j < k ~a_j = b_j </tex>.
 
}}
 
}}
  
 
Приведем псевдокод сравнения последовательностей из элементов множества '''Т''':
 
Приведем псевдокод сравнения последовательностей из элементов множества '''Т''':
  '''function''' Сompare(A, B : '''list <T>''')   <font color=green>// Возвращает "LESS", если A < B, "MORE", если A > B, или "EQUAL", если последовательности равны</font>
+
  '''function''' compare(A, B : '''list <T>'''): '''Ord'''  <font color=green>// Возвращает "LT", если A < B, "GT", если A > B, или "EQ", если последовательности равны</font>
 
   '''for''' i = 1 '''to''' min(len(A), len(B))  
 
   '''for''' i = 1 '''to''' min(len(A), len(B))  
     '''if''' A[i] < B[i]                 <font color=green> // i-й элемент А меньше i-го элемента B, но префиксы длины i - 1 равны</font>
+
     '''if''' A[i] < B[i]                     <font color=green> // i-й элемент А меньше i-го элемента B, но префиксы длины i - 1 равны</font>
       '''return''' LESS
+
       '''return''' LT
     '''if''' A[i] > B[i]                 <font color=green> // i-й элемент А больше i-го элемента B, но префиксы длины i - 1 равны</font>
+
     '''if''' A[i] > B[i]                     <font color=green> // i-й элемент А больше i-го элемента B, но префиксы длины i - 1 равны</font>
       '''return''' MORE
+
       '''return''' GT
   '''if''' len(A) < len(B)               <font color=green>// А - префикс В, но не равна ей.</font>
+
   '''if''' len(A) < len(B)                   <font color=green>// А {{---}} префикс В, но не равна ей</font>
     '''return''' LESS
+
     '''return''' LT
   '''if''' len(A) > len(B)               <font color=green>// В - префикс А, но не равна ей.</font>
+
   '''if''' len(A) > len(B)                   <font color=green>// В {{---}} префикс А, но не равна ей</font>
     '''return''' MORE
+
     '''return''' GT
   '''return''' EQUAL                      <font color=green>// Длины последовательностей и все элементы равны</font>
+
   '''return''' EQ                            <font color=green>// Длины последовательностей и все элементы равны</font>
 
{{Определение
 
{{Определение
 
|definition=Последовательности записаны в '''лексикографическом порядке''' (англ. ''lexicographical order''), если для любых <tex> i<j </tex> выполняется неравенство <tex> S_i<S_j </tex>, где <tex> S_i </tex> и <tex> S_j </tex> последовательности с номерами <tex> i </tex> и <tex> j </tex>.
 
|definition=Последовательности записаны в '''лексикографическом порядке''' (англ. ''lexicographical order''), если для любых <tex> i<j </tex> выполняется неравенство <tex> S_i<S_j </tex>, где <tex> S_i </tex> и <tex> S_j </tex> последовательности с номерами <tex> i </tex> и <tex> j </tex>.
Строка 24: Строка 23:
 
Например, слово "сон" лексикографически меньше слова "сонный", так как оно является его префиксом. Слово "низ" лексикографически меньше слова "нос", поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.
 
Например, слово "сон" лексикографически меньше слова "сонный", так как оно является его префиксом. Слово "низ" лексикографически меньше слова "нос", поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.
  
== Примеры с комбинаторными объектами ==  
+
 
 +
 
 +
 
 +
== Примеры ==
 +
* Перестановки (<font color=#c355a0>'''светло-фиолетовым выделен'''</font> общий префикс, <font color=#992574>'''темно-фиолетовым'''</font> первый отличный элемент, так как <tex>4 < 6</tex>, то первая перестановка лексикографически меньше)
 +
{| cellpadding="4" style="margin-left: left; margin-right: left;"
 +
| [[Файл:Compareperm.png]]
 +
|}
 +
* Сочетания (так как <tex>4 < 6</tex>, то первое сочетание лексикографически меньше)
 +
{| cellpadding="4" style="margin-left: left; margin-right: left;"
 +
| [[Файл:Comparechoose.png]]
 +
|}
 +
* [[комбинаторные объекты|Разбиение на слагаемые]] (так как <tex>4 < 9</tex>, то первое разбиение на слагаемые лексикографически меньше)
 
{| cellpadding="4" style="margin-left: left; margin-right: left;"
 
{| cellpadding="4" style="margin-left: left; margin-right: left;"
| [[Файл:Compareperm.png|thumb|Перестановки, общий префикс, 4 < 6, поэтому 1-ая перестановка лексикографически меньше]]
+
| [[Файл:Compare part.png]]  
| [[Файл:Comparechoose.png|thumb|Сочетания, общий префикс, 4 < 6, поэтому 1-ое сочетание лексикографически меньше]]
 
| [[Файл:Compare part.png|thumb|Разбиение на слагаемые числа 14, общий префикс, 4 > 9, поэтому 1-ое разбиение лексикографически меньше]]  
 
 
|}
 
|}
  
== Другие примеры ==
+
* Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (<tex>000</tex>, <tex>001</tex>, <tex>002</tex>, <tex>003</tex>, <tex>004</tex>, <tex>005</tex>, <tex>\dots</tex>, <tex>999</tex>).
# Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, , 999).
+
* Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок {{---}} это, например, <tex>AAA</tex>, <tex>AAB</tex>, <tex>AAC</tex>, <tex>AAD</tex>, <tex>\dots</tex>, <tex>ZZZ</tex>.
# Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок это, например, ААА, ААБ, ААВ, ААГ, , ЯЯЯ.
+
* Эти слова тоже записаны в лексикографическом порядке: <tex>airport</tex>, <tex>duck</tex>, <tex>horse</tex>, <tex>house</tex>, <tex>sleep</tex>.
# Эти слова тоже записаны в лексикографическом порядке: азбука, бог, борода, сон, сонный.
 
  
== Ссылки ==
+
== См. также ==
 +
* [[Генерация комбинаторных объектов в лексикографическом порядке]]
 +
* [[Получение предыдущего объекта]]
 +
* [[Получение следующего объекта]]
 +
== Источники информации==
 
*[http://en.wikipedia.org/wiki/Lexicographical_order Wikipedia {{---}} Lexicographical order]
 
*[http://en.wikipedia.org/wiki/Lexicographical_order Wikipedia {{---}} Lexicographical order]
 
*[http://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D0%BA%D1%81%D0%B8%D0%BA%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D0%BA Википедия {{---}} Лексикографический порядок ]
 
*[http://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D0%BA%D1%81%D0%B8%D0%BA%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D0%BA Википедия {{---}} Лексикографический порядок ]

Текущая версия на 19:03, 4 сентября 2022

Определение:
Пусть даны две последовательности [math] ~A = a_1 a_2 \dots a_n [/math] и [math] ~B = b_1 b_2 \dots b_m [/math]

Тогда последовательность [math] ~A [/math] лексикографически меньше (англ. lexicographically less) последовательности [math] ~B [/math], если выполняется одно из двух условий:

  • [math] n \lt m [/math] и при этом [math] a_i = b_i [/math] для всех [math]i \in [1 .. n] [/math],
  • [math] \exists k\leqslant \min(n, m): a_k \lt b_k [/math] и при этом [math] \forall j : j \lt k ~a_j = b_j [/math].


Приведем псевдокод сравнения последовательностей из элементов множества Т:

function compare(A, B : list <T>): Ord  // Возвращает "LT", если A < B, "GT", если A > B, или "EQ", если последовательности равны
  for i = 1 to min(len(A), len(B)) 
    if A[i] < B[i]                      // i-й элемент А меньше i-го элемента B, но префиксы длины i - 1 равны
      return LT
    if A[i] > B[i]                      // i-й элемент А больше i-го элемента B, но префиксы длины i - 1 равны
      return GT
  if len(A) < len(B)                    // А — префикс В, но не равна ей
    return LT
  if len(A) > len(B)                    // В — префикс А, но не равна ей
    return GT
  return EQ                             // Длины последовательностей и все элементы равны
Определение:
Последовательности записаны в лексикографическом порядке (англ. lexicographical order), если для любых [math] i\lt j [/math] выполняется неравенство [math] S_i\lt S_j [/math], где [math] S_i [/math] и [math] S_j [/math] последовательности с номерами [math] i [/math] и [math] j [/math].

Например, слово "сон" лексикографически меньше слова "сонный", так как оно является его префиксом. Слово "низ" лексикографически меньше слова "нос", поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.



Примеры

  • Перестановки (светло-фиолетовым выделен общий префикс, темно-фиолетовым первый отличный элемент, так как [math]4 \lt 6[/math], то первая перестановка лексикографически меньше)
Compareperm.png
  • Сочетания (так как [math]4 \lt 6[/math], то первое сочетание лексикографически меньше)
Comparechoose.png
Compare part.png
  • Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке ([math]000[/math], [math]001[/math], [math]002[/math], [math]003[/math], [math]004[/math], [math]005[/math], [math]\dots[/math], [math]999[/math]).
  • Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, [math]AAA[/math], [math]AAB[/math], [math]AAC[/math], [math]AAD[/math], [math]\dots[/math], [math]ZZZ[/math].
  • Эти слова тоже записаны в лексикографическом порядке: [math]airport[/math], [math]duck[/math], [math]horse[/math], [math]house[/math], [math]sleep[/math].

См. также

Источники информации