Изменения

Перейти к: навигация, поиск

Лексикографический порядок

125 байт добавлено, 03:04, 12 ноября 2011
Сравнение слов
Говорят, что слово <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)
if for i = 0 .. min(len(A) < , len(B)) return < if (len(B) < len(A)) return > for i = 0 .. len(A) - 1 //Длины равны, строки нумеруются с ноля
if (A[i] < B[i])
return <
if (A[i] > B[i])
return >
//все символы равныОдна из строк является префиксом другой if (len(A) < len(B)) return < if (len(A) > len(B)) return > return =//Длины строк и все символы равны
== Генерация слов в лексикографическом порядке ==
Анонимный участник

Навигация