前回のdancing linksの続きである.
TAOCP 4巻分冊0が4月18日に発売になるとアマゾンからメイルが来た. その分冊0は7章の最初の部分で, そこにGraeco-Latin squareの話題が登場する.
Graeco-Latin squareの作り方は, 互いにorthogonalな2つのlatin squareを用意し, それを合わせればよいのだが, あるlatin square Lからそれとorthogonalなlatin square Mの作り方として, Lからtransversalという組を探す. これは直接orthogonalなlatin squareを作るより容易であると本文に書いてある.
その続きは次のようだ.
Once the transversals are known, we're left with an exact cover problem, of 10 stages, which is much simpler than the original 90 stage problem (6). All we need to do is cover the square with ten transversals that don't intersect --- because every such set of ten is equivalent to a latin square M that is orthogonal to L.
10とか90とかの数値は, ここでは10x10のsquareを求めているからである.
しかしこれだけの説明では, よく分からなかったので, 考えた結果がこのblogの趣旨である.
大きいsquareは面倒なので, 4x4を対象とする.
例えば Lとして
L=((0 3 1 2)
(2 1 3 0)
(3 0 2 1)
(1 2 0 3))
は各行 各列に0,1,2,3が1回ずつ現れるから, latin squareになっている. これとorthogonalなlatin squareを求めるべく, Lのtransversalを探す. transversalはLの各行から1個 各列から1個 各文字から1個をとる組で,
A=((0 ) B=(( 3 ) C=(( 1 ) D=(( 2)
( 1 ) (2 ) ( 0) ( 3 )
( 2 ) ( 1) (3 ) ( 0 )
( 3)) ( 0 )) ( 2 )) (1 ))
E=((0 ) F=(( 1 ) G=(( 2) H=(( 3 )
( 3 ) (2 ) ( 1 ) ( 0)
( 1) ( 0 ) (3 ) ( 2 )
( 2 )) ( 3)) ( 0 )) (1 ))
の8個が存在する.
このうちA,B,C,Dを重ねるとちょうどLになり, またE,F,G,Hを重ねてもちょうどLになる.
定義が後回しになったが, LとMがorthogonalというのは, LとMから対応する位置の要素をとって組にすると, 同じ値の組が複数回は出来ないということである.
したがって各transversalの0,1,2,3の位置には0,0,0,0のように同じ値をおけば, orthogonalなlatin squareが得られる. つまり
A,B,C,Dから
M0=((0 1 2 3)
(1 0 3 2)
(2 3 0 1)
(3 2 1 0))
E,F,G,Hから
M1=((0 3 1 2)
(1 2 0 3)
(2 1 3 0)
(3 0 2 1))
ができる (LM)の組を作ると M0とM1のそれぞれから
((00 31 12 23) ((00 33 11 22)
(21 10 33 02) (21 12 30 03)
(32 03 20 11) (32 01 23 10)
(13 22 01 30)) (13 20 02 31))
が得られorthogonalなことが分かる.
Lからdancing linksでtransversalを得る方法, transversalを使わず, 直接orthogonalなlatin square(Mateという)を得る方法はTAOCP ex7-17参照のこと.
