二つのセパレータの順序付け
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/03 02:06 UTC 版)
「バードの配列表記」の記事における「二つのセパレータの順序付け」の解説
Rule A3とRule M2はよく似ているため、どのセパレーターがより高いランクなのか決定する必要がある。最初に、配列が何重にネストされたかを表す関数を L e v ( A ) {\displaystyle \mathrm {Lev} (A)} と表記する。例えば、 A = { 3 , 3 [ 1 [ 1 [ 2 ] 2 ] 2 ] 2 } {\displaystyle A=\{3,3[1[1[2]2]2]2\}} とすると、 L e v ( A ) = 3 {\displaystyle \mathrm {Lev} (A)=3} となる。つまり [ 2 ] {\displaystyle [2]} は [ 1 [ 2 ] 2 ] {\displaystyle [1[2]2]} にネストされていて、それも [ 1 [ 1 [ 2 ] 2 ] 2 ] {\displaystyle [1[1[2]2]2]} にネストされている。もう一つの関数、 N u m ( H , A ) {\displaystyle \mathrm {Num} (H,A)} を、配列 A {\displaystyle A} 中のセパレータ [ H ] {\displaystyle [H]} の個数と定義する。例えば、 A = { 3 , 3 [ 1 [ 2 ] 1 [ 2 ] 1 [ 2 ] 2 ] 2 ] 2 } {\displaystyle A=\{3,3[1[2]1[2]1[2]2]2]2\}} なら、 N u m ( 2 , A ) = 3 {\displaystyle \mathrm {Num} (2,A)=3} 。 [ A ] {\displaystyle [A]} と [ B ] {\displaystyle [B]} のどちらが優位なのかを決定する方法は、次のように表現される。 Step 1. [ A 1 ] = [ A ] , [ A 2 ] = [ A 1 ] , [ B 1 ] = [ B ] , [ B 2 ] = [ B 1 ] {\displaystyle [A_{1}]=[A],[A_{2}]=[A_{1}],[B_{1}]=[B],[B_{2}]=[B_{1}]} とする。 Step 2.もし L e v ( A ) > L e v ( B ) {\displaystyle \mathrm {Lev} (A)>\mathrm {Lev} (B)} なら、 [ A ] > [ B ] {\displaystyle [A]>[B]} 、 L e v ( A ) < L e v ( B ) {\displaystyle \mathrm {Lev} (A)<\mathrm {Lev} (B)} なら、 [ A ] < [ B ] {\displaystyle [A]<[B]} とする。 もし L e v ( A ) = L e v ( B ) > 0 {\displaystyle {\displaystyle \mathrm {Lev} (A)=\mathrm {Lev} (B)>0}} なら、Step 3へ、それ以外はStep 6へ。 Step 3. [ A ∗ ] {\displaystyle [A*]} と [ B ∗ ] {\displaystyle [B*]} をそれぞれ配列 [ A 2 ] {\displaystyle [A_{2}]} と [ B 2 ] {\displaystyle [B_{2}]} の最高位のセパレータとする。 もし [ A ∗ ] > [ B ∗ ] {\displaystyle {\displaystyle [A*]>\displaystyle [B*]}} なら [ A ] > [ B ] {\displaystyle {\displaystyle [A]>\displaystyle [B]}} 、 [ A ∗ ] < [ B ∗ ] {\displaystyle {\displaystyle [A*]<\displaystyle [B*]}} なら [ A ] < [ B ] {\displaystyle {\displaystyle [A]<\displaystyle [B]}} 、それ以外は [ H ] = [ A ∗ ] = [ B ∗ ] {\displaystyle [H]=[A*]=[B*]} としStep 4へ。 Step 4.もし N u m ( H , A 2 ) > N u m ( H , B 2 ) {\displaystyle \mathrm {Num} (H,A_{2})>\mathrm {Num} (H,B_{2})} なら、 [ A ] > [ B ] {\displaystyle [A]>[B]} 、 N u m ( H , A 2 ) < N u m ( H , B 2 ) {\displaystyle \mathrm {Num} (H,A_{2})<\mathrm {Num} (H,B_{2})} なら、 [ A ] < [ B ] {\displaystyle [A]<[B]} 、それ以外はStep 5へ。 Step 5. 文字列 A 2 {\displaystyle A_{2}} と B 2 {\displaystyle B_{2}} から、 [ H ] {\displaystyle [H]} のセパレータとその前の引数を削除する。 Step 6.これまでのルールで、 A 2 {\displaystyle A_{2}} と B 2 {\displaystyle B_{2}} は [ a ] {\displaystyle [a]} と [ b ] {\displaystyle [b]} ( a {\displaystyle a} と b {\displaystyle b} は単一の整数)の形になっているはずである。 もし [ a ] < [ b ] {\displaystyle [a]<[b]} なら [ A ] < [ B ] {\displaystyle [A]<[B]} 、 [ a ] > [ b ] {\displaystyle [a]>[b]} なら [ A ] > [ B ] {\displaystyle {\displaystyle [A]>\displaystyle [B]}} 、 それ以外はStep 7へ。 Step 7. A 1 {\displaystyle A_{1}} と B 1 {\displaystyle B_{1}} の最後の引数とその前のセパレータをすべて消去する。もし A 1 {\displaystyle A_{1}} と B 1 {\displaystyle B_{1}} がどちらも空ならば [ A ] = [ B ] {\displaystyle [A]=[B]} 、 それ以外はStep 2に戻る。
※この「二つのセパレータの順序付け」の解説は、「バードの配列表記」の解説の一部です。
「二つのセパレータの順序付け」を含む「バードの配列表記」の記事については、「バードの配列表記」の概要を参照ください。
- 二つのセパレータの順序付けのページへのリンク