tableauとbumpingについて

tableauとは次のような性質を満たすものです。
  1. 左揃え(かつ上揃え)に並んだ階段状のマス(box)のそれぞれに自然数が入っている。
  2. その自然数は左から右に向かっては広義単調増加で、上から下に向かっては狭義単調増加である。
例えば、下図のようなものがtableauです。
---------
|1|2|2|3|
|-|-|-|-|
|2|3|5|5|
|-|-|-|--
|4|4|6|
|-|-|--
|5|6|
-----

tableau Tと正整数 xについてbumpingというアルゴリズムを次のように定義します。
xが1行目のどの数よりも同じか大きければ、1行目の右にxを付け加える。
さもなくば、xより大きい数の内最も左にあるものをxに書き換え、
xを書き換えられる前の数だと思い、このアルゴリズムを次の行に適用する。
例:
---------
|1|2|2|3| ←2
|-|-|-|-|
|2|3|5|5|
|-|-|-|--
|4|4|6|
|-|-|--
|5|6|
-----



---------
|1|2|2|2|
|-|-|-|-|
|2|3|5|5| ←3
|-|-|-|--
|4|4|6|
|-|-|--
|5|6|
-----



---------
|1|2|2|2|
|-|-|-|-|
|2|3|3|5|
|-|-|-|--
|4|4|6| ←5
|-|-|--
|5|6|
-----



---------
|1|2|2|2|
|-|-|-|-|
|2|3|3|5|
|-|-|-|--
|4|4|5|
|-|-|--
|5|6| ←6
-----



---------
|1|2|2|2|
|-|-|-|-|
|2|3|5|5|
|-|-|-|--
|4|4|5|
|-|-|-|
|5|6|6|
-------

これによってできるものをT←xで表し、T←xもtableauとなります。
戻る