2

私はいくつかの完全ではないポリオミノ格子 ((最後のコメントを参照) 埋め込みグラフ (以下の例) のようなより多くの結合動物) のハッシュを構築しようとしていますが、いくつかの問題に遭遇しています。

標準的なポリオミノの場合、次のような格子埋め込みグラフがあります (テトリスを考えてください)。

  X               X
  |               |
X-X-X     or    X-X-X   or  X-X-X-X

そして、これらのようなものについては、 アルゴリズムの作業を参照して、一意のフリー ポリオミノ (またはポリオミノ ハッシュ) を識別します。

ただし、私の場合は次のとおりです。

  X                                  Y         X
  |                                  |         |     
X-Y-X  or    X-Y-X-X   or X-X-X-Y or X X X  or Y-X-X

           X
           |
or         Y-X     
           |
           X

どこで - そして | 「結合された」隣人を示す

ここで、私の場合、回転 (最初と最後など) は同じ構造であると考えていますが、2 番目と 5 番目は同じ構造であり、3 番目と 4 番目も同じ構造です。また、「フリップ」も等しいので、次のようになります。

X-X-X-Y = Y-X-X-X  and X-Y-X-X = X-X-Y-X

これらの「構造」を生成するコードは、次のように報告します。

   0  Y 0 0 0 
   1  X 1 0 0
   2  X 0 1 0
   3  X 0 0 1  
   Bonds 
   0 1
   0 2
   0 3

（2Dに投影された場合）どれが

 X
 |
 Y-X
 |
 X

構造

現在、この構造を次の文字列として解析します: YXXXb0B1 ここで、b"num" は「分岐」ポイントを示し、B"num" は分岐の数を示します。現在、B"num" は n が小さい場合 (4 ノードなど) は自明ですが、n=7 の場合は次のようになります。

  X X           X   X
  | |           |   |
X-Y-Y-X-X  or   Y-X-Y-X
                | 
                X

したがって、n=4 の場合、1 つの Y と 3 つの X がある場合、3 つの固有の構造が必要であると予想されます。

                               X
                               |
X-Y-X-X   and  Y-X-X-X  and  X-Y-X

私の現在のラベル付け/ハッシュでは、6つの「一意の構造」が得られますが、文字列操作で2つのケースを排除できると思います（最初と最後の文字を交換し、次に2つの中央の文字を交換します）が、これはおそらく排除されません重複する分岐点モデル (b1 または b0 は両方とも分岐点である可能性があり、「回転」によって分離されているだけです)。

簡単にするために、私は現在、Y のみが「分岐」できる (2 つ以上の「結合された」隣人を持つ) という追加の制限があり、最大 3 つの結合された隣人を持つという制限がある (そうではない) ラベル付きラティスに興味があります。典型的なポリオミノはすべて含まれます)。実際、それらは「構造」や結合格子アニマルのようなポリオミノの奇妙なクロスであり、格子ツリー (ループ/サイクルなし) に似ています (リンクを参照: http://www.ms.unimelb.edu.au/~andrewr/ research/intro_html/node8.html )。

編集：

フォローアップとして、次のルールを使用してこれらの構造のいずれかを記述することで解決したと思いました: (+ = 連結)

番号。ブランチの + ブランチ ID (ランダムに割り当てられた) + そのブランチのシーケンス + 次のブランチ ID + シーケンス .... など。しかし、これはまだうまくいきません。

しかし、これで十分かどうかはまだわかりません。Yが3つ以上の結合された隣人を持つ場合、それは機能しないことを私は知っていますが、Yの結合された隣人<= 3の私の限られたケースでは機能するようです。

4

0 に答える 0