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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
м (rollbackEdits.php mass rollback)
 
(не показана 31 промежуточная версия 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=Последовательности записаны в '''лексикографическом порядке''' ''(in 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>.
 
}}
 
}}
 
Например, слово "сон" лексикографически меньше слова "сонный", так как оно является его префиксом. Слово "низ" лексикографически меньше слова "нос", поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.
 
Например, слово "сон" лексикографически меньше слова "сонный", так как оно является его префиксом. Слово "низ" лексикографически меньше слова "нос", поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.
 +
 +
 +
  
 
== Примеры ==
 
== Примеры ==
# Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999).
+
* Перестановки (<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;"
 +
| [[Файл:Compare part.png]]
 +
|}
  
== Ссылки ==
+
* Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (<tex>000</tex>, <tex>001</tex>, <tex>002</tex>, <tex>003</tex>, <tex>004</tex>, <tex>005</tex>, <tex>\dots</tex>, <tex>999</tex>).
 +
* Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок {{---}} это, например, <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://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://en.wikipedia.org/wiki/Lexicographical_order 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 Википедия {{---}} Лексикографический порядок ]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Комбинаторика ]]
 
[[Категория: Комбинаторика ]]

Текущая версия на 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].

См. также

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