Определение лексикографического порядка?

Question

В настоящее время я читаю о функции std::next_permutation и столкнулся с термином "лексикографический порядок". В то время у меня не было никакого опыта с этим термином, так что гугл поискал это и нашел только несколько загадочные определения этого типа заказа, включая статью в вики (по крайней мере, они для меня).

Так кто-нибудь может попытаться помочь мне понять это? Что такое "хорошее" определение этого термина для вас?

Что касается статьи в вики - они утверждают, что лексикографический порядок также известен как алфавитный порядок, но когда я продолжаю читать, я понимаю, что они не совпадают. Таким образом, продолжающееся сравнение меня немного смущает.

Answer 1

При обычном использовании английского языка, когда мы сортируем слова в алфавитном порядке, мы применяем два правила:

• Если два слова имеют одну и ту же первую букву, мы сравниваем второе. Если вторые буквы совпадают, мы сравниваем третью и т. Д. Наконец, одно слово стоит перед другим, если первая отличающаяся буква идет перед соответствующей буквой.

• Если два слова идентичны по длине более короткого слова, более короткое слово идет первым.

Так что "Том" предшествует "Зубу". Первые буквы идентичны ("T"), вторые буквы - "o", но третьи буквы diff и "m" идут перед "o". Поэтому "Том" предшествует "Зубу".

"Том" стоит перед "Томас", потому что два слова идентичны через первые три буквы "Том", а "Том" короче, чем "Томас".

Лексикографический порядок - это просто алфавитный порядок, обобщенный для не буквенных значений. Рассмотрим последовательность значений, а не обязательно букв:

(1,5,10) предшествует (1,6,3), потому что "5" предшествует "6".

(1,5,10) предшествует (1,5,10,15,20), потому что (1,5,10) короче (1,5,10,15,20).

Лексикографическое упорядочение особенно полезно, если элементы последовательности имеют определенное значение, причем более ранние значения имеют более высокий приоритет. Например, рассмотрим эти времена: 9:13 утра и 8:25 утра. Если мы представим их в последовательности (9,13) и (8,25), то (8,25) предшествует (9,13), потому что 8 предшествует 9. Что если часы совпадают? Например, (9,13) предшествует (9,45), потому что 13 предшествует 45. Как вы можете видеть, лексикографическое упорядочение позволяет полю часов иметь более высокий приоритет, чем поле минут.

Answer 2

Большинство встроенных алгоритмов сортировки строк реализованы в виде лексикографической сортировки. (Подробнее на дне)

Пример 1:

Случайные элементы:

['A','a','a','B','b','C','c','d','E']

Сортировка с лексикографическим порядком:

['A','B','C','E','a','a','b','c','d']

Пример 2:

Случайные элементы с разной длиной:

['a', 'b', 'aa', 'c', 'ddd', 'f']

Сортировка с лексикографическим порядком:

['a', 'aa', 'b', 'c', 'ddd', 'f']

Разница между лексикографическим и натуральным типом

input = ["z1.txt", "z10.txt", "z3.txt", "z100.txt", "z101.txt"]

lexicogrpahic : ['z1.txt', 'z10.txt', 'z100.txt', 'z101.txt', 'z3.txt']
natural: ['z1.txt', 'z3.txt', 'z10.txt', 'z100.txt', 'z101.txt']

Мы могли бы вдаваться в детали, но многие великие люди уже создали отличные объяснения этому:

1) Есть ли в Python встроенная функция для естественной сортировки строк?

2) https://blog.codinghorror.com/sorting-for-humans-natural-sort-order/

Answer 3

С точки зрения непрофессионала, это означает алфавитный порядок. На практике вы будете сортировать строки символ за символом в соответствии с их числовым представлением (обычно ASCII).