辞書式順序の実装方法

辞書式順序というのは、まあ辞書に載ってるような単語の順序で並べろという話である
辞書式順序

単純なアルファベットによる辞書式順序ソート

Array#sortすると、アルファベット順に並んでくれる

irb(main):008:0> ["alpine", "africa", "blue", "china"].sort
=> ["africa", "alpine", "blue", "china"]

数学の文脈における辞書式順序

単項式順序

数学の話でも辞書式順序というものが出てくる。多項式の中で単項式の項順序を定めて、ソートするというものだ。

辞書式順序 (lexicographic order, lex) の 数学的な前提

β - α の 0 でない最初の成分が正である場合に x^α < x^β として定義される単項式順序である。

素朴に表現するならば、lex 順序はまず最も「上位の」不定元の指数の大きさによって順序付け、

それが同じものについては順次「下位の」不定元の指数の大きさによって順序付ける。

先に、xとyについて辞書式順序の例を挙げると以下のようになる

\[ 1 \prec y \prec y^2 \prec \cdots \prec x \prec xy \prec xy^2 \prec \cdots x^2 \prec x^2y \prec \cdots x^3 \cdots \]

解説なしに \( \prec \) を使ったが、「グレブナー基底の計算基礎編計算代数入門」, p82 より以下のようなことが言える

集合における順序 \( \prec \) とは大小関係を一般化したものと考えてよい

この記号は使う数学の文脈で意味が異なるので注意が必要だ。WEB上で定義が見つからないので、Wolframへのリンクを引用する：

Precedes
- The relationship x precedes y is written x≺y. The relation x precedes or is equal to y is written x<=y.
- xがyに先行する関係はx≺yと書かれています。関係xはyに先行するか、yに等しいと、x <= yと記述されます。
Succeeds
- The relationship x succeeds (or follows) y is written x≻y. The relation x succeeds or is equal to y is written x>=y.
- 関係xは〜に続きます yはx≻yと書かれます。関係xは続くか、yと等しいとx> = yと記述されます。

もう一度例に戻ると

先に、xとyについて辞書式順序の例を挙げると以下のようになる（また、１の場合の注訳をつけた）

\[ (先行) \space 1 (= x^0y^0) \prec y \prec y^2 \prec \cdots \prec x \prec xy \prec xy^2 \prec \cdots x^2 \prec x^2y \prec \cdots x^3 \cdots (後行)　\]

例からわかる暗黙の前提
- このprecedes/succeedsは、集合を昇順/降順(asc/desc)で見たとき昇順(asc)で先行しているという意味を前提として持っているようだ。昇順(asc)は小さいものが先にくる。
- また、\( y \prec x \space OR \space x \succ y \) が先に定義されている←これは単にXのほうがYより大きいということ

辞書式順序 (lexicographic order, lex) の実装

さて、順序が定義できたところでどういう風にしたいか考えると

さっきの例の逆で項は並んでほしいので、ソートしたら降順(desc)になってほしい
- まあRubyのArray#sortはデフォルトで昇順なので、昇順でソートしといてあとでreverseする感じで

\[ x^3, x^2y, x^2, xy^2, xy, x, y^2, y, 1 (= x^0y^0) \]

項順序は任意で定義したい
- ただ、普通のアルファベット順だとaとかbがx,yより前に来てしまうので、x, y, zのようなよく使うやつは大きいものと定義しておこう

\[ x \succ y \succ z \succ u \succ v \succ w \succ p \succ q \succ r \succ s \succ t \succ a \succ b \succ c \succ d \succ e \succ f \succ g \succ h \succ i \succ j \succ k \succ l \succ m \succ n \succ o \]

実装
- ソート対象の係数は無いものとして考える
- ソート対象の多項式は"変数を文字列、べき指数を数値としてもつ連想配列"として考える

VarOrder = ["x", "y", "z", "u", "v", "w", "p", "q", "r", "s", "t", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o"]

# x^3, x^2y, x^2, xy^2, xy, x, y^2, y, 1 (= x^0y^0)
polynomial_to_order = [{"x"=>3}, {"x"=>2, "y"=>1}, {"x"=>1, "y"=>2}, {"x"=>1, "y"=>1}, {"y"=>2}, {"y"=>1}, {}]

polynomial_to_order.sort do |lhs,rhs|
  ret = 0
  for var in VarOrder
    if lhs[var].to_i - rhs[var].to_i != 0
       ret = lhs[var].to_i <=> rhs[var].to_i
       break
    end
  end
  ret
end

# テスト
irb(main):215:0> polynomial_to_order = [{}, {"y"=>1}, {"y"=>2}, {"x"=>1}, {"x"=>1, "y"=>1}, {"x"=>1, "y"=>2}, {"x"=>2}, {"x"=>2, "y"=>1}, {"x"=>3}]

irb(main):215:0> polynomial_to_order.shuffle!
=> [{"x"=>3}, {"x"=>2, "y"=>1}, {"x"=>2}, {"x"=>1, "y"=>2}, {"y"=>2}, {}, {"x"=>1}, {"x"=>1, "y"=>1}, {"y"=>1}]

irb(main):216:1* polynomial_to_order.sort do |lhs,rhs|
irb(main):217:1*   ret = 0
irb(main):218:2*     for var in VarOrder
irb(main):219:3*         if lhs[var].to_i - rhs[var].to_i != 0
irb(main):220:3*           ret = lhs[var].to_i <=> rhs[var].to_i
irb(main):221:3*           break
irb(main):222:2*         end
irb(main):223:1*     end
irb(main):224:1*     ret
irb(main):225:0> end
=> [{}, {"y"=>1}, {"y"=>2}, {"x"=>1}, {"x"=>1, "y"=>1}, {"x"=>1, "y"=>2}, {"x"=>2}, {"x"=>2, "y"=>1}, {"x"=>3}]

辞書式順序の実装方法