アルゴリズムを解析しろと言われた気がした?ので。
このページはYNy Sequence(Y数列の定義になった、嬉しい)のアルゴリズムの解説?ページです。ソースはここにあります。WIPです。
注意: 自分のJavaScriptのソースコードはあまりきれいとは言えません。また、このプログラムはwhY mountainに使われた関数や概念、表現を流用しており、非常にわかりにくい可能性があります。その場合は質問してください。
単語[]
mountain[]
Mt.Fuji、及びそれらのプログラム内部での表現につけられる。ここではY数列用語の山(mountain)とは異なる。#calcMountain(s)を参照。
diagonal[]
斜め階差数列。
seam[]
Mt.Fujiにおいて左上-右下方向の斜線。左から0から順番に番号が付けられる。Y数列に対応する概念は名付けられていない。
height[]
数字にかかっているの場合Mt.Fuji内の高さ。オリジナルの数列から0から数える。Mt.Fujiやseamにかかっている場合はそれの高さ。
index[]
このページではmountain内部横位置。Mt.Fujiで空欄になっているものは数えない。
position[]
Mt.Fujiで横位置。空欄を含めて数える。
親、子、右下、左下、左上、左[]
a b / \ / \ c d e
このような山の集合があるとき、
- cはdの親、dはeの親
- dはcの子、eはdの子
- dはaの右下、eはbの右下
- cはaの左下、dはbの左下
- aはdの左上、aはdの左上
- aはbの左、cはdの左、dはeの左
そして、任意のa,b,cに対して次が成り立つ。
- aがbの親であることとbがaの子であることは同値
- aがbの右下であることとbがaの左上であることは同値
- [aに右下が存在せずaがbの親]または[aがbの左上かつbがcの左下である]こととaはbの左であることは同値
- aがbの左下かつbがcの左上であることとaはcの親であることは同値
- aがbの左上ならばaのposition+1=bのposition
怒る親[]
#刈られる子の祖先で、展開に重要である。#getBadRoot(s)を参照。
悪い部分[]
展開でコピーされる部分。刈られる子を除いた#怒る親から右の部分となる。
良い部分[]
#怒る親より左の部分。
刈られる子[]
最も右の数。展開するとこれが除かれるされるため。
コピペ[]
右下のindexを検索[]
/* mountain - mountain(入力) height - 右下を見つける要素のheight(入力) index - 右下を見つける要素のindex(入力) output - 右下のindex(出力) mountain[height-1][output]がmountain[height][index]の右下となる */ var output=0; while (mountain[height-1][output].position!=mountain[height][index].position+1) output++;
ある数の右下のindexと言えばこれに適切な変数を入れた時の出力のことである。
左上のindexを検索[]
/* mountain - mountain(入力) height - 左上を見つける要素のheight(入力) index - 左上を見つける要素のindex(入力) output - 左上のindex(出力) 左上が存在すればmountain[height-1][output]がmountain[height][index]の左上となる */ var output=0; while (mountain[height+1][output]&&mountain[height+1][output].position<mountain[height][index].position-1) output++;
上と同じ。ただし、これが存在するとは条件の不等号を等号へ変えたものが成り立つという意味である。
あるheightで与えられたpositionを持つ数を検索[]
/* mountain - mountain(入力) height - 見つける要素のheight(入力) position - 見つける要素のposition(入力) output - 見つける要素のindex(出力) 指定の位置に数が存在すればmountain[height][output]が指定の要素となる */ var output=0; while (mountain[height][output]&&mountain[height][output].position<position) output++;
上と同じ。
あるheightで与えられたseam内の数を検索[]
/* mountain - mountain(入力) height - 見つける要素のheight(入力) seam - 見つける要素のseam番号(入力) output - 見つける要素のindex(出力) 指定の位置に数が存在すればmountain[height][output]が指定の要素となる */ var output=0; while (mountain[height][output]&&mountain[height][output].position+height<seam) output++;
上と同じ。
グローバル変数[]
アルゴリズムに関係するもののみ書きます。
itemSeparatorRegex[]
2行目で定義。Stringタイプの数列を数ごとに分けるのに使われる。
関数[]
アルゴリズムに関係するもののみ書きます。
parseSequenceElement(s,i)[]
15行目で定義。sはStringタイプの数やvを使った表現、iはindex。次のようなObjectを返す。sに"v"が含まれるとき、vの後の数が親を指定している。
{
value:<数値>,
position:<Mt.Fujiにおける位置>,
parentIndex:<vが使われていないとき-1、そうでないとき指定された親の内部位置>,
forcedParent:<vによって親が強制的に指定されたか>
}
calcMountain(s)[]
calcMountain("1,2,4,8,10,8")
32行目で定義。sはStringタイプもしくはArrayタイプの数列。mountainを返す。
mountainはArrayで、下から順に横列は(Array)が格納されている。また、横列はそれぞれ数が左から順に#parseSequenceElement(s,i)の出力のような形に並べられている。例えば数列1,2,4,8,10,8は次で表される(whY mountainの出力と照らし合わせると良い)。
[
[
{
"value":1,
"position":0,
"parentIndex":-1
},
{
"value":2,
"position":1,
"parentIndex":0
},
{
"value":4,
"position":2,
"parentIndex":1
},
{
"value":8,
"position":3,
"parentIndex":2
},
{
"value":10,
"position":4,
"parentIndex":3
},
{
"value":8,
"position":5,
"parentIndex":2
}
],
[
{
"value":1,
"position":0,
"parentIndex":-1
},
{
"value":2,
"position":1,
"parentIndex":0
},
{
"value":4,
"position":2,
"parentIndex":1
},
{
"value":2,
"position":3,
"parentIndex":0
},
{
"value":4,
"position":4,
"parentIndex":1
}
],
[
{
"value":1,
"position":0,
"parentIndex":-1
},
{
"value":2,
"position":1,
"parentIndex":0
},
{
"value":1,
"position":2,
"parentIndex":-1
},
{
"value":2,
"position":3,
"parentIndex":0
}
],
[
{
"value":1,
"position":0,
"parentIndex":-1
},
{
"value":1,
"position":2,
"parentIndex":-1
}
]
]
以下「数」とは基本mountainの要素の要素のことを指す。
- 34行目。lastLayerに配列に変換したsを代入(#itemSaparaterRegexで数を分けそれぞれに#parseSequenceElement(s,i)を適応する)し、calculatedMountainに[lastLayer]を代入する。このときまだ親は探索していない。
- 40-84行目。1行ずつmountainを計算していくルーチン。
- 41-74行目。lastLayerの親情報を埋めるルーチン。iをそのindexとする。なお、親が存在しない場合parentIndexは-1となる。
- 44行目。もしforcedParentなら親を検索しない。
- 48行目。もし1行目ならばpをindex+1(position+1と等しい)、それ以外ならばpを右下のindexとする。
- 55-73行目。右下の祖先を辿り親を探索するルーチン。右下の祖先の左上で値が小さいもので一番右にあるものが親である。
- 56行目。p<0ならば右下の祖先は全て見た後のため親は存在しないとし終了する。
- 58行目。1行目の場合p=p-1としてからj=p-1とする。それ以外の場合pを次の右下の祖先のindexにし、p<0でないならばjをその左上のindex、p<0ならば親は存在しないとし終了する。
- 67行目。もしp<0もしくは2行目以降のとき参照している右下の祖先の左上lastLayer[j]の一つ左のposition(この左は上で定義したものとは異なる)に数がない場合、つまりこの右上の祖先に親がない場合は親は存在しないとして終了する。
- 68行目。この右下の祖先の左上の値lastLayer[j]がlastLayer[i]より小さいとき、lastLayer[j]が親であるとして終了する。そうでない場合この操作を繰り返す。
- 75行目。もしlastLayerに親を持つ数がない場合次の行は空のため終了する。
- 76行目。lastLayerで親を持つ数の左上にそれぞれの親との差を置いた新たな行をlastLayerの上に置き、lastLayerの参照先をこれに変更する。繰り返す。
- 41-74行目。lastLayerの親情報を埋めるルーチン。iをそのindexとする。なお、親が存在しない場合parentIndexは-1となる。
- 85行目。形成したmountainを返す。
calcDiagonal(mountain)[]
calcDiagonal("1,3,8,17,12,8")
87行目で定義。sはmountain。Stringタイプでdiagonalを返す。
- 88行目。diagonalとdiagonalTreeに空のArrayを代入する。diagonalは斜め階差数列の値、diagonalTreeには左+左下方向の親的関係が表さられる。
- 90-121行目。seamごとに計算する。
- 122行目。配列pwにもしdiagonalを素朴な数列としたときの親(左にあり数が小さいもので最も右のもの)のindexを順に置く。
- 133行目。配列rにdiagonalのそれぞれの要素(i番目とする)に対しp=iとし、p=diagonalTree[p]をdiagonal[p]<diagonal[i]になるまで繰り返す。これは通常の親の探索にさらにdiagonalTreeで生成したときの操作を使ってたどり着くという条件を課しているということである。そして、rに数を追加、pwで計算したものと親が異なればvを使いcalcMountainを適応するとき親を変更させるようにする。
- 144行目。rの要素をコンマで接続した文字列を返す。
cloneMountain(mountain)[]
146行目で定義。sはmountain。クローンされたmountainを返す。そのまま別の変数に代入して扱うと同じオブジェクトが共有されてしまうため。
getBadRoot(s)[]
162行目で定義。sはStringタイプの数列もしくはmountain。怒る親のseamの番号を返す。
- 163行目。sをmountainにし(mountainに代入)、diagonalをとる(diagonalに代入)。
- 167行目。diagonalの最も右の数が1より大きいならばgetBadRoot(diagonal)を返す。
- 169行目。そうでないならばmountainの最も左のseamで最も高い位置にある数を探し、その左下の数のseam番目を返す。
図必要?WIP
expand(s,n,stringify)[]
expand("1,3,4,2,5,11,6,8,12,5",3)
175行目で定義。sはStringタイプの数列もしくはmountain、nはNumberタイプのn、stringifyはBooleanタイプで出力をStringタイプにするかどうか。s[n]を文字列もしくはmountainで返す。
- 176行目。sをmountainにしmountainに代入する。また、mountainをクローンしてresultに代入する。
- 180行目。もし刈られる子に親が存在しなければ(インフォーマルに後続順序数ならば)resultから刈られる子を削除する。
- 182行目。そうでない場合、
- 184行目。cutHeightに刈られる子のseamのheightを代入する。
- 186行目。actualCutHeightにcutHeightを代入する。
- 187行目。badRootSeamにgetBadRoot(mountain)を代入する。以下seamの意味でbadRootSeamといったときはbadRootSeam番目のseamとする。
- 189行目。diagonalにcalcMountain(calcDiagonal(mountain))を代入する。
- 191行目。yamakazi(展開規則が山火事であるかのフラグ)をdiagonalの刈られる子が1であれば建てる。yamakaziならば山火事、そうでなければ噴火である。
- 192行目。もしyamakaziならばnewDiagonalをdiagonalから刈られる子を削除しbadRootSeamから右(badRootSeamを含むが、刈られる子を含まない)を右にn個コピーして追加する。そして、cutHeightを1減らしてから、badRootHeightにcutHeightを代入する。newDiagonalはmountainが崩壊しているが問題ない。
- 202行目。yamakaziでない(噴火する)ならば、newDiagonalをexpand(diagonal,n,false)と再帰的に計算し、badRootHeightをbadRootSeamのheightとする。
- 212行目。刈られる子をresultから取り除く。もし一番高い横列が空になる場合削除する。
- 214行目。afterCutHeightにこの地点でのresultのheight、afterCutMountainにこの地点のresultのクローン、afterCutLengthにこの地点のresultの長さを代入する。
- 225-377行目。展開結果のmountainの枠組みを作る。特に、mountainの形と親の情報を計算し、元のmountainに無かった部分は山肌をnewDiagonalで埋めていく。それ以外の部分は最後に値を計算する。
- 226-377行目。悪い部分をコピーしながらiを1づつ増やしていく(1<=i<=n)。これはあるiの時i個目の悪い部分のコピーを足していく作業である。
- 227-376行目。悪い部分をseamごとに分けてコピーしていく。jをコピー元のseam番号(badRootSeam<=i<afterCutLength)とする。
- 228-245行目。このseamが噴火によって(右)上に伸びるかどうかのフラグをisAscendingに立てる。そのseamでheightがbadRootHeightの数の祖先にbadRoot(seamではなくbadRootSeamとbadRootHeightで与えられる1つの数)があるかどうかで判定する。
- 230行目。seamでheightがbadRootHeightな数のindexを探し、pに代入する。
- 231-242行目。もし上で探索した数が存在する場合、
- 243行目。もし存在しない場合、isAscendingではない。
- 246行目。seamHeightを今のコピー元のseamのheightとする。
- 254行目。今のコピー元のseamがbadRootSeamである時、isReplacingCutである。
- 256行目。isAscendingの場合。
- 257行目。k(0<=k<seamHeight+(cutHeight-badRootHeight)*i)を増やしていく。kは数のコピー先のheightである。
- 258行目。もしresultのheightがk未満の場合上に配列を足す。
- 259-279行目。k<badRootHeightの場合。B_b。
- 260行目。sy=kとする。sxをisReplacingCutならmountain[sy].length-1、そうでないならば現在のseamでheightがsyな数のindexとする。mountain[sy][sx]はコピー元の数である。
- 268行目。sourceParentIndexをコピー元の親のindexとし、parentShiftsをisReplacingCutならばi-1、そうでないならばiとした時、parentPositionをコピー元の親が存在するならばコピー元の親のposition+parentShifts*(コピー元の親が悪い部分に含まれるならばafterCutLength-badRootSeam、そうでないならば0)-(k-sy)、存在しなければ-1とし、parentIndexにresultでheightがkでpositionがparentPosition(つまり、親のコピー先)に存在すればそのindex、なければ-1(存在しない)を代入する。
- 274行目。result[k]の末尾に値が親が存在しなければ(山肌)そのnewDiagonalでj+(afterCutLength-badRootSeam)*i個目の数の値でそうでなければNaN(不明)、positionがj+(afterCutLength-badRootSeam)*i-k、parentIndexがparentIndex、forcedParentがコピー元のforcedParentを引き継いだ数を追加する。
- 280-300行目。上でなくk<=badRootHeight+(cutHeight-badRootHeight)*(isReplacingCutならばi-1、そうでなければi)の場合。B_rで刈られる子を有った部分の置換。
- 281行目。sy=badRootHeightとする。sxをyamakaxiでなくかつisReplacingCutならmountain[sy].length-1、そうでないならば現在のseamでheightがsyな数のindexとする。mountain[sy][sx]はコピー元の数である。
- 289行目。sourceParentIndexをコピー元の親のindexとし、parentShiftsをisReplacingCutならばi-1、そうでないならばiとした時、parentPositionをコピー元の親が存在するならばコピー元の親のposition+parentShifts*(コピー元の親が悪い部分に含まれるならばafterCutLength-badRootSeam、そうでないならば0)-(k-sy)、存在しなければ-1とし、parentIndexにresultでheightがkでpositionがparentPosition(つまり、親のコピー先)に存在すればそのindex、なければ-1(存在しない)を代入する。
- 295行目。result[k]の末尾に値が親が存在しなければ(山肌)そのnewDiagonalでj+(afterCutLength-badRootSeam)*i個目の数の値でそうでなければNaN(不明)、positionがj+(afterCutLength-badRootSeam)*i-k、parentIndexがparentIndex、forcedParentがコピー元のforcedParentを引き継いだ数を追加する。
- 301-321行目。上でなくisReplacingCutかつk<=badRootHeight+(cutHeight-badRootHeight)*iの場合。B_rでかつ刈られる子の有ったseamで上へ増える時。
- 302行目。sy=k-(cutHeight-badRootHeight)*(i-1)とする。sxをyamakaziでなくかつisReplacingCutならmountain[sy].length-1、そうでないならば現在のseamでheightがsyな数のindexとする。mountain[sy][sx]はコピー元の数である。
- 310行目。sourceParentIndexをコピー元の親のindexとし、parentShiftsをisReplacingCutならばi-1、そうでないならばiとした時、parentPositionをコピー元の親が存在するならばコピー元の親のposition+parentShifts*(コピー元の親が悪い部分に含まれるならばafterCutLength-badRootSeam、そうでないならば0)-(k-sy)、存在しなければ-1とし、parentIndexにresultでheightがkでpositionがparentPosition(つまり、親のコピー先)に存在すればそのindex、なければ-1(存在しない)を代入する。
- 316行目。result[k]の末尾に値が親が存在しなければ(山肌)そのnewDiagonalでj+(afterCutLength-badRootSeam)*i個目の数の値でそうでなければNaN(不明)、positionがj+(afterCutLength-badRootSeam)*i-k、parentIndexがparentIndex、forcedParentがコピー元のforcedParentを引き継いだ数を追加する。
- 322-344行目。上でない場合。B_e。
- 324行目。sy=k-(cutHeight-badRootHeight)*iとする。sxをyamakaziでなくかつisReplacingCutならmountain[sy].length-1、そうでないならば現在のseamでheightがsyな数のindexとする。mountain[sy][sx]はコピー元の数である。
- 332行目。sourceParentIndexをコピー元の親のindexとし、parentShiftsをisReplacingCutならばi-1、そうでないならばiとした時、parentPositionをコピー元の親が存在するならばコピー元の親のposition+parentShifts*(コピー元の親が悪い部分に含まれるならばafterCutLength-badRootSeam、そうでないならば0)-(k-sy)、存在しなければ-1とし、parentIndexにresultでheightがkでpositionがparentPosition(つまり、親のコピー先)に存在すればそのindex、なければ-1(存在しない)を代入する。
- 338行目。result[k]の末尾に値が親が存在しなければ(山肌)そのnewDiagonalでj+(afterCutLength-badRootSeam)*i個目の数の値でそうでなければNaN(不明)、positionがj+(afterCutLength-badRootSeam)*i-k、parentIndexがparentIndex、forcedParentがコピー元のforcedParentを引き継いだ数を追加する。
- 257行目。k(0<=k<seamHeight+(cutHeight-badRootHeight)*i)を増やしていく。kは数のコピー先のheightである。
- 346-374行目。もしisAscendingで無い場合。
- 348行目。k(0<=k<seamHeight)を増やしていく。kは数のコピー先のheightである。
- 349行目。もしresultのheightがk未満の場合上に配列を足す。
- 351-373行目。全ての場合。B_b。
- 352行目。sy=kとする。sxをisReplacingCutならmountain[sy].length-1、そうでないならば現在のseamでheightがsyな数のindexとする。mountain[sy][sx]はコピー元の数である。
- 360行目。sourceParentIndexをコピー元の親のindexとし、parentShiftsをisReplacingCutならばi-1、そうでないならばiとした時、parentPositionをコピー元の親が存在するならばコピー元の親のposition+parentShifts*(コピー元の親が悪い部分に含まれるならばafterCutLength-badRootSeam、そうでないならば0)-(k-sy)、存在しなければ-1とし、parentIndexにresultでheightがkでpositionがparentPosition(つまり、親のコピー先)に存在すればそのindex、なければ-1(存在しない)を代入する。
- 366行目。result[k]の末尾に値が親が存在しなければ(山肌)そのnewDiagonalでj+(afterCutLength-badRootSeam)*i個目の数の値でそうでなければNaN(不明)、positionがj+(afterCutLength-badRootSeam)*i-k、parentIndexがparentIndex、forcedParentがコピー元のforcedParentを引き継いだ数を追加する。
- 348行目。k(0<=k<seamHeight)を増やしていく。kは数のコピー先のheightである。
- 227-376行目。悪い部分をseamごとに分けてコピーしていく。jをコピー元のseam番号(badRootSeam<=i<afterCutLength)とする。
- 378-391行目。mountainの内側を左から右に横列を上から埋めていく。
- 379-391行目。iをresultのheight-1から0まで1づつ減らしていく。iは現在埋めているheightである。
- 393行目。stringifyの場合、rrをresultの数列部分の数をforcedParentならば値+”v”+親のposition、そうでなければ値を順に並べ間にコンマを置いた文字列とする。
- 399行目。そうでない場合、rrにresultを代入する。
- 402行目。rrを返す。