Лексикографический порядок — различия между версиями
Flanir (обсуждение | вклад) |
Flanir (обсуждение | вклад) (→Примеры) |
||
Строка 35: | Строка 35: | ||
| [[Файл:Comparechoose.png]] | | [[Файл:Comparechoose.png]] | ||
|} | |} | ||
− | * [[комбинаторные объекты| | + | * [[комбинаторные объекты|Разбиение на слагаемые]] |
{| cellpadding="4" style="margin-left: left; margin-right: left;" | {| cellpadding="4" style="margin-left: left; margin-right: left;" | ||
| [[Файл:Compare part.png]] | | [[Файл:Compare part.png]] | ||
Строка 43: | Строка 43: | ||
* Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок {{---}} это, например, <tex>AAA</tex>, <tex>AAB</tex>, <tex>AAC</tex>, <tex>AAD</tex>, <tex>\dots</tex>, <tex>ZZZ</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>airport</tex>, <tex>duck</tex>, <tex>horse</tex>, <tex>house</tex>, <tex>sleep</tex>. | ||
+ | |||
== См. также == | == См. также == | ||
* [[Генерация комбинаторных объектов в лексикографическом порядке]] | * [[Генерация комбинаторных объектов в лексикографическом порядке]] |
Версия 01:30, 31 декабря 2014
Определение: |
Пусть даны две последовательности Тогда последовательность лексикографически меньше (англ. lexicographically less) последовательности , если выполняется одно из двух условий:
| и
Приведем псевдокод сравнения последовательностей из элементов множества Т:
function compare(A, B : list <T>) // Возвращает "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), если для любых | выполняется неравенство , где и последовательности с номерами и .
Например, слово "сон" лексикографически меньше слова "сонный", так как оно является его префиксом. Слово "низ" лексикографически меньше слова "нос", поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.
Примеры
- Перестановки
- Сочетания
- Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке ( , , , , , , , ).
- Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, , , , , , .
- Эти слова тоже записаны в лексикографическом порядке: , , , , .
См. также
- Генерация комбинаторных объектов в лексикографическом порядке
- Получение предыдущего объекта
- Получение следующего объекта