辞書順

数学において、辞書順（または辞書順序とも呼ばれる）とは、辞書のアルファベット順を、順序付けられた記号の列、あるいはより一般的には、完全に順序付けられた集合の要素の列に一般化したものである。

辞書式順序付けにはいくつかのバリエーションと一般化が存在する。その一つは、要素を考慮する前にシーケンスの長さを比較することで、長さの異なるシーケンスに適用できるものである。

別の方法として、組み合わせ論で広く用いられている方法では、与えられた有限集合に全順序を割り当て、部分集合を昇順列に変換し、その列に辞書式順序を適用することで、与えられた有限集合の部分集合に順序を付ける。

一般化では、部分的に順序付けられた集合のn項直積上の順序を定義します。この順序は、直積のすべての因子が全順序である場合に限り、全順序となります。

語彙集（ある言語で使用される単語の集合）に含まれる単語は、辞書や百科事典などで用いられる慣習的な順序付けに従っており、その順序は単語を構成する記号のアルファベットの基となる順序に依存している。語彙順序は、基となる記号の順序に基づいて単語の順序を形式化する一つの方法である。

形式的な概念は、有限集合A（しばしばアルファベットと呼ばれる）から始まる。この集合は全順序である。つまり、A内の異なる2つの記号aとbに対して、a < bまたはb < aのいずれか一方だけが真となる。

Aの単語とは、 Aからの有限個の記号列であり、1つの記号を含む長さ1の単語、2つの記号を含む長さ2の単語など、空のシーケンスも含む。${\displaystyle \varepsilon }$記号は一切使用しない。これらすべての有限語の集合における辞書式順序は、単語を次のように並べる。

1. 長さが同じで異なる 2 つの単語、例えばa = a ₁ a ₂ ... a _kとb = b ₁ b ₂ ... b _kが与えられた場合、2 つの単語の順序は、2 つの単語が異なる最初の位置iの記号のアルファベット順(単語の先頭から数えて) に依存します。a < bは、アルファベットAの基となる順序でa _i < b _iの場合に限ります。
2. 2つの単語の長さが異なる場合、通常の辞書順では、短い方の単語の末尾に「空白」（Aのすべての要素よりも小さいものとして扱われる特別な記号）を追加して、単語の長さを同じにしてから、前のケースと同様に単語を比較します。

しかし、組み合わせ論では、2番目のケースに対して別の慣例がよく用いられ、短いシーケンスは常に長いシーケンスよりも小さいとされます。この辞書式順序の変形は、ショートレックス順序と呼ばれることもあります。

辞書順では、「Thomas」は「Thompson」より前に表示されます。これは、両者が最初に異なる文字が5番目の文字（「a」と「p」）であり、アルファベット順では「a」が「p」より前に来るためです。最初の違いであるため、この場合、5番目の文字がアルファベット順における「最も重要な違い」となります。

辞書式順序の重要な性質は、各nに対して、長さnの単語の集合が辞書式順序によって整列されていることです(アルファベットが有限である場合)。つまり、長さnの単語の任意の減少列は有限です (または同等に、すべての空でない部分集合には最小の要素があります)。^{[ 1 ] [ 2 ]}すべての有限の単語の集合が整列されているとは限りません。たとえば、単語の無限集合 {b, ab, aab, aaab, ... } には、辞書式順序で最初の要素がありません。

辞書の語順は、辞書だけでなく、数字や日付にも一般的に用いられている。

ローマ数字体系の欠点の1つは、2つの数字のうちどちらが小さいかをすぐに判断できないことです。一方、ヒンドゥー・アラビア数字体系の位取り記数法では、自然数の自然順序が辞書式順序の短縮形と同じであるため、数字の比較は容易です。実際、位取り記数法では、自然数は数字の列で表され、ある自然数が別の自然数よりも大きいのは、桁数が多い場合（先頭のゼロは無視）、または桁数が同じで、異なる最初の（最上位の）桁が大きい場合です。

十進数表記の実数では、辞書式順序とは少し異なる順序が用いられます。小数点の左側の部分はこれまでと同様に比較され、等しい場合は、小数点の右側の部分が辞書式順序と比較されます。この場合の「空白」とは、末尾の「0」のことです。

負の数も考慮に入れる場合、負の数を比較する際の順序を逆にする必要があります。これは通常、人間にとっては問題になりませんが、コンピュータにとっては問題となる可能性があります（符号の判定に時間がかかるため）。これが、コンピュータで符号付き整数を表現する際に2の補数表現を採用する理由の一つです。

辞書以外の用途で辞書式順序が使われている例として、日付の形式をYYYY-MM-DDで表すISO 8601規格が挙げられます。この書式設定方式の利点は、日付を表す文字列の辞書式順序が時系列順と一致することです。つまり、より古い日付は、より新しい日付よりも辞書式順序で小さく表示されます。これは西暦1年から西暦9999年までの日付に当てはまります。この日付順序により、別途ソートアルゴリズムを用意する必要がなくなり、コンピュータによる日付のソートが容易になります。

アルファベットA上の単語のモノイドは、 A上の自由モノイドです。つまり、モノイドの要素はAの要素の有限列 (単語) (長さ 0 の空列を含む) であり、演算 (乗算) は単語の連結です。単語uは、 v = uwとなる単語wが存在する場合、別の単語vの接頭辞(または「切り捨て」)です。この定義により、空単語 (${\displaystyle \varepsilon }$）はすべての単語の接頭辞であり、すべての単語はそれ自体の接頭辞である（w付き）${\displaystyle =\varepsilon }$これらのケースを除外する場合は、注意が必要である。

この用語を用いると、上記の辞書式順序の定義はより簡潔になります。部分的にまたは完全に順序付けられた集合Aと、 A上の2 つの単語aとbがあり、 bが空でないとすると、以下の条件のうち少なくとも 1 つが満たされる場合、辞書式順序においてa < bとなります。

• aはbの接頭辞である
• 単語u、v、w （空の場合もあり）とAの要素xおよびyが存在し、

x < y

a = uxv

b = uyw

この定義の接頭辞条件により、${\displaystyle \varepsilon <b\,\,{\text{すべての }}b\neq \varepsilon に対して}$どこ${\displaystyle \varepsilon }$それは空虚な言葉である。

もし${\displaystyle \,<\,}$は全順序です${\displaystyle A,}$すると、単語の辞書順も${\displaystyle A.}$しかし、一般的にこれは整列したものではなく、アルファベットが${\displaystyle A}$整列している。例えば、A = { a , b }の場合、言語{ a ⁿ b | n ≥ 0, b > ε } は、辞書式順序で最小要素を持たない: ... < aab < ab < b。

多くのアプリケーションでは整列が求められるため、辞書式順序の変形がよく使用されます。この整列順序は、ショートレックスまたは準辞書式順序と呼ばれることもあり、まず単語の長さを考慮します（長さ( a ) < 長さ( b )の場合、${\displaystyle a<b}$)、長さが同じ場合は辞書順を使用します。Aの順序が整列順序である場合、ショートレックス順序についても同様です。^{[ 2 ] [ 3 ]}

辞書式順序は、順序付けられた集合のn項直積上の順序を定義します。これらの集合がすべて全順序である場合、それは全順序となります。直積の要素${\displaystyle E_{1}\times \cdots \times E_{n}}$は、${\displaystyle i}$^th要素は${\displaystyle E_{i}}$すべての${\displaystyle i.}$シーケンスの辞書式順序を評価する際には、シーケンス内で同じランクを持つ要素のみを比較するため、辞書式順序は順序付けられた集合のデカルト積にも拡張されます。

具体的には、2 つの部分的に順序付けられた集合が与えられた場合${\displaystyle A}$そして${\displaystyle B,}$のデカルト積の辞書式順序${\displaystyle A\times B}$は次のように定義される。 $${\displaystyle (a,b)\leq \left(a^{\prime },b^{\prime }\right){\text{ は }}a<a^{\prime }{\text{ または }}\left(a=a^{\prime }{\text{ かつ }}b\leq b^{\prime }\right{ の場合に限る } }$$

結果は半順序です。${\displaystyle A}$そして${\displaystyle B}$2つの要素がそれぞれ全順序集合である場合、結果として得られる要素も全順序集合となる。したがって、2つの全順序集合の辞書式順序は、それらの積順序の線形拡張となる。

無限個の順序付き集合の直積についても同様に辞書式順序を定義できる。ただし、その集合が自然数で添え字付けされている場合、あるいはより一般的には整列集合で添え字付けされている場合に限る。この一般化された辞書式順序は、各因子集合が全順序付けされている場合に全順序となる。

有限の場合とは異なり、整列順序の無限積は必ずしも辞書式順序で整列されているとは限りません。例えば、可算無限二進数列の集合（定義により、自然数から への関数の集合）${\displaystyle \{0,1\},}$カントール空間としても知られる${\displaystyle \{0,1\}^{\オメガ }}$) は整列していません。${\displaystyle 1}$（つまり、{ 100000..., 010000..., 001000..., ... }）は、によって誘導される辞書式順序の下で最小要素を持たない。${\displaystyle 0<1,}$なぜなら100000... > 010000... > 001000... > ...は無限下降鎖だからである。^{[ 1 ]}同様に、無限辞書式積もネーター的ではない。なぜなら011111... < 101111... < 110111 ... < ...は無限上昇鎖だからである。

整列集合からの関数${\displaystyle X}$完全に順序付けられた集合へ${\displaystyle Y}$インデックス付きの配列で識別される可能性があります${\displaystyle X}$要素の${\displaystyle Y.}$したがって、それらは辞書順で並べることができ、そのような2つの関数に対して${\displaystyle f}$そして${\displaystyle g,}$辞書順は、最小値の値によって決定される。${\displaystyle x}$そのため${\displaystyle f(x)\neq g(x).}$

もし${\displaystyle Y}$また、整然としており、${\displaystyle X}$が有限であれば、結果として得られる順序は整列順序となる。上記のように、${\displaystyle X}$無限であるというのは、そうではない。

組み合わせ論では、与えられた集合の有限部分集合を列挙し、順序付けることがしばしば必要となる。${\displaystyle S.}$そのためには、通常は次の注文を選択します。${\displaystyle S.}$次に、サブセットをソートします${\displaystyle S}$これは、それを増加数列に変換することと同等です。結果として得られる数列の辞書式順序は、部分集合の順序を誘導し、これも辞書式順序と呼ばれます。

この文脈では、一般的には、ショートレックス順序のように、まず部分集合を要素数でソートすることが好まれます。したがって、以下では、固定された要素数の部分集合に対する順序のみを考慮します。

例えば、整数の自然順序を使用して、3 つの要素のサブセットの辞書式順序付けを行うと、${\displaystyle S=\{1,2,3,4,5,6\}}$は

123 < 124 < 125 < 126 < 134 < 135 < 136 < 145 < 146 < 156 <

234 < 235 < 236 < 245 < 246 < 256 < 345 < 346 < 356 < 456。

自然数の与えられた濃度の有限部分集合を順序付ける場合、共辞書式順序（下記参照）の方が便利な場合が多い。なぜなら、すべての初期セグメントは有限であり、したがって共辞書式順序は自然数と集合の集合との間の順序同型を定義するからである。${\displaystyle n}$自然数。これは辞書式順序には当てはまりません。辞書式順序では、例えば、${\displaystyle 12n<134}$すべての${\displaystyle n>2.}$

させて${\displaystyle \mathbb {Z} ^{n}}$階数の自由アーベル群である${\displaystyle n,}$その要素は、${\displaystyle n}$整数であり、演算は加算です。${\displaystyle \mathbb {Z} ^{n}}$は全順序であり、加算と互換性がある。 $${\displaystyle a<b\quad {\text{ は a+c<b+c の場合に限る。}$$

辞書順はグループ順です${\displaystyle \mathbb {Z} ^{n}.}$

辞書順は、すべてのグループ順を特徴付けるためにも使用できます。${\displaystyle \mathbb {Z} ^{n}.}$^{[ 4 ] [ 5 ]}実際、${\displaystyle n}$実数係数を持つ線形形式からマップを定義します${\displaystyle \mathbb {Z} ^{n}}$の中へ${\displaystyle \mathbb {R} ^{n},}$形式が線形独立であれば単射となる（形式が従属の場合でも単射となる場合がある。下記参照）。このマップの像の辞書式順序は、群順序を誘導する。${\displaystyle \mathbb {Z} ^{n}.}$ロビアーノの定理とは、あらゆる群の位数をこの方法で求めることができるという定理である。

より正確には、${\displaystyle \mathbb {Z} ^{n},}$整数が存在する${\displaystyle s\leq n}$そして${\displaystyle s}$実数係数を持つ線形形式、誘導写像${\displaystyle \varphi }$から${\displaystyle \mathbb {Z} ^{n}}$の中へ$\displaystyle \mathbb {R} ^{s}}$以下の特性を持つ。

• ${\displaystyle \varphi }$単射である。
• 結果として生じる同型性${\displaystyle \mathbb {Z} ^{n}}$のイメージへ${\displaystyle \varphi }$画像に辞書式順序が付与されている場合、これは順序同型写像である。$\displaystyle \mathbb {R} ^{s}.$

コレキシコグラフィー順序またはコレックス順序は、有限シーケンスを左から右に読むのではなく、右から左に読むことによって得られる辞書順序の変形である。より正確には、2 つのシーケンス間の辞書順序は次のように定義される。

a ₁ a ₂ ... a _k < ^lex b ₁ b ₂ ... b _k最初のiでa _iとb _{i が}異なる場合、 a _i < b _i

共語彙順序は次のように定義される。

a ₁ a ₂ ... a _k < ^colex b ₁ b ₂ ... b _k最後のiについてa _i < b _iの場合、 a _iとb _iが異なる

一般的に、共辞書順と辞書順の差はそれほど大きくありません。しかし、特に部分集合の符号化など、増加順序を考慮する場合、両者の順序は大きく異なります。

例えば、2 つの自然整数の増加数列 (または集合) を順序付ける場合、辞書式順序は次のように始まります。

12 < 13 < 14 < 15 < ... < 23 < 24 < 25 < ... < 34 < 35 < ... < 45 < ...、

そして共語彙順序は

12 < 13 < 23 < 14 < 24 < 34 < 15 < 25 < 35 < 45 < ...。

与えられた長さの増加数列の共辞書式順序の主な性質は、すべての開始セグメントが有限であることです。言い換えれば、与えられた長さの増加数列の共辞書式順序は、自然数との順序同型を誘導し、これらの数列を列挙することを可能にします。これは組み合わせ論で頻繁に使用され、たとえばクラスカル・カトナの定理の証明で使用されています。対照的に、上記の辞書式順序における省略記号はそれぞれ無限の数列を省略するため、たとえば、 23で終わる開始セグメントは無限になります。

多項式を考える場合、一般的には項の順序は関係ありません。なぜなら、加算は可換だからです。しかし、多項式の長除法などの一部のアルゴリズムでは、項が特定の順序になっている必要があります。多変数多項式の主要なアルゴリズムの多くは、グレブナー基底に関連しています。グレブナー基底とは、単項式の順序、つまり全順序を選択する必要がある概念であり、これは単項式のモノイド構造と互換性があります。ここで「互換性がある」とは、${\displaystyle a<b{\text{は}ac<bcを意味する}$モノイド演算が乗法的に表記される場合。この互換性は、多項式と単項式の積が項の順序を変えないことを意味します。グレブナー基底の場合、さらに条件を満たす必要があります。すなわち、定数でないすべての単項式は単項式1より大きいということです。ただし、この条件は、接錐の計算アルゴリズムなど、他の関連アルゴリズムには必要ありません。

グレブナー基底は固定数の変数の多項式に対して定義されるため、単項式（例えば）を同一視することが一般的です。${\displaystyle x_{1}x_{2}^{3}x_{4}x_{5}^{2}}$）とその指数ベクトル（ここでは[1, 3, 0, 1, 2]）です。nが変数の数である場合、すべての単項式の順序は、次の制限になります。${\displaystyle \mathbb {N} ^{n}}$単項式の次数${\displaystyle \mathbb {Z} ^{n}}$（上記§ 亜鉛のグループオーダーを参照）${\displaystyle \mathbb {Z} ^{n},}$分類のため）。

許容される順序の一つに、辞書式順序がある。これは歴史的に見て、グレブナー基底を定義するために最初に用いられた順序であり、辞書式順序に関連する他の順序と区別するために、純粋辞書式順序と呼ばれることもある。

もう一つの方法は、まず総次数を比較し、次に辞書式順序を用いて矛盾を解決するというものです。しかし、この順序は広く用いられていません。なぜなら、辞書式順序または次数逆辞書式順序の方が一般的に優れた特性を持っているからです。

次数逆辞書式順序は、まず総次数を比較し、総次数が等しい場合は、共辞書式順序の逆を使用することから成ります。つまり、2 つの指数ベクトルが与えられた場合、1 つは $${\displaystyle [a_{1},\ldots ,a_{n}]<[b_{1},\ldots ,b_{n}]}$$ どちらか $${\displaystyle a_{1}+\cdots +a_{n}<b_{1}+\cdots +b_{n},}$$ または $${\displaystyle a_{1}+\cdots +a_{n}=b_{1}+\cdots +b_{n}\quad {\text{ かつ }}\quad a_{i}>b_{i}{\text{ は、}}a_{i}\neq b_{i} を満たす最大の }}i{\text{ に対して成り立つ。}$$

この順序付けでは、1次の単項式は対応する不定元と同じ順序になります（逆辞書式順序を使用した場合はそうはなりません）。同じ総次数を持つ2変数の単項式を比較する場合、この順序は辞書式順序と同じです。変数がもっと多い場合はそうではありません。たとえば、3変数の2次の単項式の指数ベクトルについては、次数逆辞書式順序は次のようになります。 $${\displaystyle [0,0,2]<[0,1,1]<[1,0,1]<[0,2,0]<[1,1,0]<[2,0,0]}$$

辞書式順序の場合、同じ指数ベクトルは次のように順序付けられます。 $${\displaystyle [0,0,2]<[0,1,1]<[0,2,0]<[1,0,1]<[1,1,0]<[2,0,0]。}$$

次数逆辞書式順序の有用な性質は、同次多項式が最小不定多項式の倍数であるのは、その先頭の単項式（より大きな単項式）がこの最小不定多項式の倍数である場合に限る、という点である。

• 照合
• クリーネ・ブロワー順序
• 辞書式選好― 経済学における辞書式順序の応用。
• 辞書式最適化とは、辞書式上で最大の要素を見つけるアルゴリズム問題である。
• 単位正方形上の辞書式順序トポロジー
• テンソル抽象インデックス表記における辞書式順序付け
• 辞書的に最小限の弦の回転
• レキシミンを注文する
• 長い線（トポロジー）
• リンドンの言葉
• 先行順序–二分木走査における（ビットの）辞書順の名称
• スタープロダクト– 部分注文を組み合わせる別の方法
• Shortlexの注文
• 完全順序集合のデカルト積の順序

• Wikiversityにある、辞書順序と共辞書順序に関する学習教材