データ構造のアドバイスをお願いします。

３点×３点（２辺×２辺）固定で、静的構造でいきたいなら、中心を原点にして、時計回りの原則で辺に２次元の番号をつけると思います。

漢字だと逆回りになりますが（それでもいいけど趣味の問題）以下のごとく。

(0,0)(0,1)(0,2)(0,3)が（十）

(1,0)(1,1)(1,2)(1,3)が加わって（卍）、

(2,0)(2,1)(2,2)(2,3)が加わって格子（田）

それぞれが値を持つのなら２次元の配列で扱う。こうすれば反転や回転の同一性がみやすいかなと。

４点×４点（３辺ｘ３辺）以上に拡張することを将来想定するなら、上記の手は破綻しそうなので、□を単位として、あえて１６本に増やしたデータ構造にして、４本が重複していることは別途処理にすると思います。

□□

□□

各□の位置は(0,0)(0,1)(1,0)(1,1)で表現して、□の各辺に(0,1,2,3)の番号つけて、

左上の□の右辺(0,0,1)と右上の□の左辺(0,1,3)が共通であることは

メソッドを通じて常に同時更新を保証するような感じで。

(0,0,1)=(0,1,3), (0,0,2)=(1,0,0), (0,1,2)=(1,1,0), (1,0,1)=(1,1,3)

どう考えても辺に番号付けて存在ビットがよさそうです。なので役立たないと思ったらポイントはお返しします。ビット・ローテーション命令とビット順反転命令が使えれば楽のようです。

記述が楽なのでここでは漢字と矢印で名づけます。

┏亥┳丑┓

戌‥↑‥寅

┣←╋→┫

申‥↓‥辰

┗未┻巳┛

ここで→を寅＝辰の特殊な型とみなし、以下同様に↓：巳未、←：申戌、↑：亥丑とみなすと、→↓←↑の処理を｛丑寅　辰巳　未申　戌亥｝とほぼ同一に出来ます。つまり｛→↓←↑｝は｛↑→→↓　↓←←↑｝としておきます。するとどの大きさの格子も｛丑寅　辰巳　未申　戌亥｝の組に分解できます。

ここで回転は｛丑寅　辰巳　未申　戌亥｝８ビットに対し２ビット・ローテーションします。こうすればテーブルを使わずに済みますが、使えない場合はテーブル化もやむを得ません。

0000 0000→｛0000 0000｝→0000 0000

0100 0000→｛0000 0001｝→0000 0100

1000 0000→｛0000 0010｝→0000 1000 etc.　256通り

反転は｛丑寅　辰巳　未申　戌亥｝の左右が｛亥戌　申未　巳辰　寅丑｝になります。上下は不要。ビット順反転命令が使えれば楽ですが、使えない場合はやはりテーブルの出番でしょう。

｛0000 0000｝←→0000 0000

｛0000 0001｝←→1000 0000

｛0000 0010｝←→0100 0000 etc.　256通り

各々｛↑→→↓　↓←←↑｝でも大丈夫なことを確かめてください。

この演算を駆使して回転反転で同一視できる８つ（か４つか２つか１つ）のもののうち、辞書順で最小のものを選び代表データとすればいいと思います。

【結論】｛｛↑→→↓　↓←←↑｝｛丑寅　辰巳　未申　戌亥｝｝の１６ビットをお勧めします。

45度回転して、辺の有り無しを行列に格納するのはどうですか？

□／＼□

／＼／＼

＼／＼／

□＼／□

と見るわけです。

たとえば、上の図のようにすべて辺がある場合には

0110 1111 1111 0110になります。

回転しての一致を調べるのは楽です。上下・左右の反転は

多少面倒かな。

行列への格納の仕方はいろいろあるでしょうけど、４５度回転式だと直感的だし、格子数数が増えた場合も自然に拡張できるので悪くないと思います。

９０度ほかの回転の比較はこんなやり方できれいに書けるかと。

回転０の基底ベクトルがx0 = [1,0], y0 = [0, 1]、９０度の場合はx1 =[0, 1], y1 = [-1, 0], 180度はx2 = [-1,0], y2 = [0, -1], 270度がx = [-1,0], y = [1,0]とおけて、

for(i=0;i<3;i++) for(j=0; j<3;j++) if (mat( i * x0 %4, j * y0 % 4) == mat(i * x1 % 4 , j* y1 % 4) ) {一致している}

などといったループで一致をみるわけです。%は剰余。

上下左右反転の場合も基底ベクトルをいじればできると思います。

なるほど。束（ラティス）はやはりこの方向で見るべきなんですね^o^

上下反転は y=x　を中心に反転する行列、

左右反転は y=-x を中心に反転する行列でよさそうですね。

（逆か？まあ本質的ではない^o^）

１０ｘ１０程度なら、ビット毎比較ではねなくても、反転や回転を施してから引き算してもメモリからの読み出しとかの方が大きそうですから、そこでの工夫は効果が薄そうです。

辺の本数のような回転や反転での不変量をインデクスに使うのは良い手段で、計算量向上に役にたつと思います。

全体の辺の本数のほか、中心部分の部分格子、つまり中心から距離１以内の本数、２以内の本数、といった量も回転や反転に対して変化しないので使えるでしょう。でも、全体の辺の本数によほど偏りがなければ、母集団が１０００組や１万組になってから考えてもいいと思います。

確かにデーター・回転計算・反転計算をシンプルにしようとすれば行列は最適だと思います。しかし重複チェックをしようとするとどうしても数バイトにわたってしまいます。

しかし１６ビット（１２ビット）格納方式ならそのまま１６ビット整数値の比較だけで済みますし、重複チェックのためにテーブル参照方式を使うことになっても６４ＫＢ（か４ＫＢ）だけと負担少なく使用できます。

個人的には格子が巨大化したときの計算量の増大も気になります。行列式だと実装次第では回転反転計算量は辺の本数の１～３乗に比例しかねませんが、予め格子全体を｛丑｝｛寅｝　｛辰｝｛巳｝　｛未｝｛申｝　｛戌｝｛亥｝という８つのリストに分解しておけば、回転反転計算量はポインタの交換操作分だけ、つまり常に定数にできます。まあこの質問では計算量は考慮外のようですが。