字典序

字典序是指按照單詞首個字母順序在字典中進行排序的方法。在數學中可推廣到有序符號序列，可視為完全有序集合的元素序列的一種排序方法。

字典序有多種變體和推廣，一種變體在考慮序列元素之前先比較序列的長度。另一種變體廣泛用於組合學，通過為有限集指定全序來對子集進行排序，並將子集轉換為應用字典序的遞增序列。

字典序可以推廣定義偏序集的笛卡爾積的順序， 若且唯若笛卡爾積的所有因子都全序時，該順序才是全序。

概念

在英文字典中，排列單詞的順序是先按照第一個字母以升序排列（即a、b、c……z 的順序）；如果第一個字母一樣，那就比較第二個、第三個乃至後面的字母。如果比到最後兩個單詞不一樣長（比如，sigh 和 sight），那麼把短者排在前。

通過這種方法，我們可以給予本不相關的單詞強行規定出一個順序。「單詞」可以看作是「字母」的字符串，而把這一點推而廣之就可以認為是給對應位置元素所屬集合分別相同的各個有序多元組規定順序。

形式定義

給定兩個偏序集A和B，(a,b)和(a′,b′)屬於笛卡爾積 A × B，則字典序定義為

(a,b) ≤ (a′,b′) 若且唯若 a < a′ 或 (a = a′ 且 b ≤ b′).

結果是偏序。如果A和B是全序, 那麼結果也是全序。

多個集合乘積的場合

上面的定義可以拓展：只要兩個元素屬於 A₁×A₂×...×A_n 這個笛卡爾積，或者可寫成 X=(x₁, x₂, ..., x_n) 和 Y=(y₁, y₂, ..., y_n) 的有序多元組形式，那麼兩者即可排序——從前往後：

• 如果 x₁ 和 y₁ 沒有順序（按照 A₁上的偏序，下同）：那麼 X 和 Y 沒有順序。
• 否則，如果 x₁ 在 y₁ 之前，那麼 X 在 Y 之前；反之若 y₁ 在 x₁ 之前，那麼 Y 在 X 之前。
• 否則 x₁ 和 y₁ 不分先後。接下來討論 x₂ 和 y₂、x₃ 和 y₃等等。

X 和 Y 甚至可以不一樣長：只要對應位置的元素所屬的集合相同（第一個位置的元素都屬於 A₁ 集合、第二個位置的元素都屬於 A₂ 集合、等等），即可套用上面的做法。如果比到後面發現兩者之一的元素先耗盡了，那麼可視情況規定短者排在前或在後。

對於英語單詞來說，單詞可以說是在笛卡爾積 A×A×A×... 這個集合上的多元組（其中集合 A 是二十六個英文字母的集合），那麼在字典中排列單詞的順序就是這裡說的字典序——這也就是「字典序」這個名稱的由來。

舉例來說，全排列 {1,2,3} 按照字典序的下一個排列分別是 123、132、213、231、312 和 321。如果就數字集合 {1, 2, 3, ..., n} 的排列而言，這個集合的全排列本身可以看成是 n+1 進制的數，這種情況下，所有排列的字典序等價於所有按照全排列順序把數字寫成的數集合的升序。