我正在尝试构建一些不完全多联格的哈希(更多的债券动物,如(见最后的评论)嵌入式图(下面的示例),但遇到了一些问题。
对于标准的多米诺骨牌,我们有像这样的格子嵌入图(想想俄罗斯方块):
X X
| |
X-X-X or X-X-X or X-X-X-X
对于这样的事情,我只会参考 Algorithm 的工作来识别唯一的免费多骨牌(或多骨牌哈希)
但是,就我而言,我有以下内容:
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
在哪里 - 和 | 表示“绑定”的邻居
现在,就我而言,我认为任何旋转(例如第一个和最后一个)都是相同的结构,而第二个和第五个是相同的,第三个和第四个也是相同的结构。“翻转”也相等,所以:
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 个案例(交换第一个和最后一个字符,然后交换两个中间字符),但这可能不会消除重复的分支点模型(b1 或 b0,都可以是分支点并且只是由“旋转”分隔)。
作为简化,我目前只对标记格子感兴趣,这些格子具有只有 Y 可以“分支”(具有 2 个以上“键合”邻居)的额外限制,并且它们具有最多键合 3 个邻居的限制(所以不所有典型的多骨牌都将包括在内)。事实上,它们是像“结构”和键格动物这样的多合体的奇怪交叉,类似于格子树(没有循环/循环)(参见链接:http ://www.ms.unimelb.edu.au/~andrewr/研究/intro_html/node8.html)。
编辑:
作为后续,我认为我已经通过使用以下规则来描述这些结构中的任何一个来解决它:(+ = concatenate)
编号。分支 + 分支 ID(随机分配)+ 该分支中的序列 + 下一个分支 id + 序列 .... 等等。但这仍然行不通。
但我仍然不确定这是否足够。我知道在 Y 有超过 3 个保税邻居的情况下,它不起作用,但对于我有限的 Y 保税邻居 <=3 的情况,它似乎工作。