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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сравнение слов)
м (rollbackEdits.php mass rollback)
 
(не показано 55 промежуточных версий 8 участников)
Строка 1: Строка 1:
== Определение ==
+
{{Определение
Пусть дано линейно упорядоченное множество <tex>~E=\{e_1<e_2<e_3<...<e_k\}</tex> {{---}} алфавит. Словом назовем упорядоченное множество <tex> ~S </tex> элементов алфавита <tex> ~A </tex>. Тогда если на алфавите <tex> A </tex> задан порядок, то порядок задан и на слове <tex> ~S </tex>. Тогда говорят, что множество слов <tex> ~A </tex> задано в лекcикографическом порядке, если для <tex>\forall i \in A </tex> <tex>\forall j \in A </tex> таких, что <tex> i < j </tex> выполнено, что слово <tex> ~A_i </tex> меньше, чем слово <tex> ~A_j </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> '''лексикографически меньше''' (англ. ''lexicographically less'') последовательности <tex> ~B </tex>, если выполняется одно из двух условий:
 +
*<tex> n < m </tex> и при этом <tex> a_i = b_i </tex> для всех <tex>i \in [1 .. n] </tex>,
 +
* <tex> \exists k\leqslant \min(n, m): a_k < b_k </tex> и при этом <tex> \forall j : j < k ~a_j = b_j </tex>.
 +
}}
  
== Сравнение слов ==
+
Приведем псевдокод сравнения последовательностей из элементов множества '''Т''':
Что же значит, что слово <tex> ~A </tex> меньше слова <tex> ~B </tex>, и как вообще можно сравнивать слова?
+
'''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))
 +
    '''if''' A[i] < B[i]                    <font color=green> // i-й элемент А меньше i-го элемента B, но префиксы длины i - 1 равны</font>
 +
      '''return''' LT
 +
    '''if''' A[i] > B[i]                    <font color=green> // i-й элемент А больше i-го элемента B, но префиксы длины i - 1 равны</font>
 +
      '''return''' GT
 +
  '''if''' len(A) < len(B)                    <font color=green>// А {{---}} префикс В, но не равна ей</font>
 +
    '''return''' LT
 +
  '''if''' len(A) > len(B)                    <font color=green>// В {{---}} префикс А, но не равна ей</font>
 +
    '''return''' GT
 +
  '''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>.
 +
}}
 +
Например, слово "сон" лексикографически меньше слова "сонный", так как оно является его префиксом. Слово "низ" лексикографически меньше слова "нос", поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.
  
Говорят, что слово <tex> ~A </tex> меньше слова <tex> ~B </tex>, если:
 
  
1. Длина (количество элементов) слова <tex> ~A </tex> меньше длины слова <tex> ~B </tex>
 
  
2. Длины слов равны, но <tex>\exists i </tex>  <tex> \ge 0 </tex> такое, что для всех <tex> j < i </tex> выполнено неравенство <tex> A_j = B_j </tex>, а <tex> A_i < B_i </tex>. Элементы слова мы можем сравнивать, так как это элементы алфавита, а на алфавите задан строгий порядок.
 
  
Приведем псевдокод сравнения слов:
+
== Примеры ==
function isEqual(A, B : string)
+
* Перестановки (<font color=#c355a0>'''светло-фиолетовым выделен'''</font> общий префикс, <font color=#992574>'''темно-фиолетовым'''</font> первый отличный элемент, так как <tex>4 < 6</tex>, то первая перестановка лексикографически меньше)
    if (len(A) < len(B))
+
{| cellpadding="4" style="margin-left: left; margin-right: left;"
        return <
+
| [[Файл:Compareperm.png]]
    if (len(B) < len(A))
+
|}
        return >
+
* Сочетания (так как <tex>4 < 6</tex>, то первое сочетание лексикографически меньше)
    for i = 0 .. len(A) - 1 //Длины равны, строки нумеруются с ноля
+
{| cellpadding="4" style="margin-left: left; margin-right: left;"
        if (A[i] < B[i])
+
| [[Файл:Comparechoose.png]]  
            return <
+
|}
        if (A[i] > B[i])
+
* [[комбинаторные объекты|Разбиение на слагаемые]] (так как <tex>4 < 9</tex>, то первое разбиение на слагаемые лексикографически меньше)
            return >
+
{| cellpadding="4" style="margin-left: left; margin-right: left;"
    //все символы равны
+
| [[Файл:Compare part.png]]
    return =
+
|}
  
== Генерация слов в лексикографическом порядке ==
+
* Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (<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>.
  
Параметром для рекурсии будет служить префикс, который мы уже записали. Тогда если наш префикс уже длины <tex> L </tex> (которую мы хотим получить), то запишем получившееся слово, и выйдем из рекурсии. Если длина меньше, то будем приписывать по символу, в порядке от меньшего к большему и снова запускать рекурсию от нового префикса.
+
== См. также ==
 +
* [[Генерация комбинаторных объектов в лексикографическом порядке]]
 +
* [[Получение предыдущего объекта]]
 +
* [[Получение следующего объекта]]
 +
== Источники информации==
 +
*[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 Википедия {{---}} Лексикографический порядок ]
  
Почему это будет работать? Ну давайте проверим определение: мы генерируем слова одинаковой длины, потому проверим пункт 2.
+
[[Категория: Дискретная математика и алгоритмы]]
  
Пусть мы сейчас имеем префикс длины <tex> i </tex> и все строки, начинающихся с префиксов меньших, чем наш уже выведены. Тогда согласно алгоритму мы будем приписывать меньшие символы, и достраивать при помощи рекурсии их до полных строк, то есть перебирать все строки с новым префиксом. А так как мы приписываем символы по увеличению, то все слова с меньшим префиксом мы заведомо переберем, следовательно слова будут в лексикографическом порядке.
+
[[Категория: Комбинаторика ]]
 
 
Приведем псевдокод генерации:
 
procedure generate(s : string)
 
    if (len(s) == L)
 
        write(s);
 
        exit;
 
    for i = 'a' .. 'z'
 
        generate(s + i)
 
 
 
 
 
== Примеры ==
 
# Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999).
 
# Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ.
 

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

См. также

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