找到一个包含所有可能的3x3位模式的NxM网格

8
更新:这被称为de Brujin环,但我仍然需要找出一个简单的C#算法。

http://en.wikipedia.org/wiki/De_Bruijn_torus

http://datagenetics.com/blog/october22013/index.html


我需要尽可能密集地组合一个3x3位网格的所有值。通过3x3位网格,我的意思是一个3x3的网格,每个位置都类似于这个问题中的卡片孔概念:

查找所有3x3卡片孔的组合

3x3位网格示例:

XXX .X. ...
XXX .X. .X.
XXX .X. ...

目标

我希望将所有512个(实际上只有256个,因为中心位始终打开)可能的值打包在一个NxM网格中,使它们重叠。

不完整示例:

此示例将大约25个可能的值打包到一个7x7网格中。

.......
.X.XXX.
.......
.X.XXX.
.X.XXX.
.X.XXX.
.......

已知事项:

  • 有2^9 (512)个独特的值。
  • 我只关心2^8 (256)个值,因为我需要中心位始终为开启状态。

尝试

我手动尝试了许多不同的技术,但无法想出简单的算法。

因此,我想编写一个C#程序来创建它,但我也没有看到简单的方法。

甚至没有明显的暴力方法对我来说似乎是可能的。在最坏的情况下,任何暴力尝试都会接近512!组合。

观察

每个边缘只有8个可能的值。

X...X.XXX. //(8+2 bits) Exhausts all values in the same problem with 1-Dimension.

.X.XXX.    //(5+2 bits) The above simplifies when the center bit must be on. 

目的

这将用于2D基于块状图的游戏。

游戏有N种可能的地面元素。考虑到地形可以出现在任何情况下,设计师需要一种表达每个给定情况下应选择哪个瓦片的方法。

一个包含每种可能情况的紧凑网格是指定在每种情况下使用哪个瓦片最有效的方法,并消除了所有冗余。

更新

示例

....
.XX.
.XX.
....

上面是基本模式,可以表达4种情况,我将修改它以使用其他ASCII值来表示应在每种情况下使用的结果:
....
.AG.
.HH.
....

A、G、H分别代表应使用的特定模式,适用于每种情况。

因此,如果出现以下模式:

...
.XX
.XX

这与产生 'A' 的模式相匹配,因此在该情况下将使用 'A'。
???
?A?
???

目的是对每种可能情况进行详尽的表达,以便得出结果。

实践中

我曾尝试过这样做,但发现结果太随机,无法很好地达到目标。作为人类,由于组织不当,在每种情况下选择正确的值是困难的。手动分组相似模式仍然更有效。


当你说“紧凑”时,是指在存储网格时需要小于512位(64字节)吗? - Martin
@j_random_hacker 它可以是任何大小的NxM,包括3xM。理想情况下,它应该易于人类阅读,但这并不是我的主要关注点。 - Rick Love
啊,我不知道打包意味着非重叠...使用您建议的标题。 - Rick Love
2
你能详细说明一下网格如何在实时中被访问吗?在我看来,从0到511的数字不仅表达了所有的9位模式,而且它们本身就是这些模式。 - גלעד ברקן
作为一种优化策略,这是徒劳无功的(因为C语言运行的平台已经越来越少)。 - DarthGizka
显示剩余7条评论
3个回答

3

用De Bruijn序列将所有3x3模式打包成一个3xN网格

让我们把每个高度为3的列看作是一个介于0和7之间的单个数字,因为有8种可能的高度为3的列。现在,将所有512种可能的3x3模式打包成最小可能的3xN尺寸网格等同于找到一个参数为B(8,3)的De Bruijn序列。这个网格的大小将是 3x514 :在第一个3x3之后,每个额外的3x3只会花费我们1个额外的列,这显然是高度为3的网格的最佳选择。

根据维基百科页面,似乎最有效的方法是通过在先前序列的De Bruijn图中找到欧拉环来构建一系列De Bruijn序列B(8,1),B(8,2),B(8,3)(因为另一个建议算法涉及查找哈密顿路径,这是与旅行商问题难度相当的NP完全问题)。

还有De Bruijn环面,它们是De Bruijn序列的二维类比,更直接地逼近了您将内容打包到NxN网格中的目标。但是从该页面上并不清楚如何或者说是否可能为3x3模式构造De Bruijn环面(他们只说已知可以为偶数大小的正方形模式构造,而奇数大小的正方形模式的环面本身不能是正方形-因此大概率NxN不可行),而且,它们满足的强唯一性约束对于您的应用程序来说可能是不必要的。


嗯,这比每个512个3x3网格都列出来要更有效率一些。它将工作量减少了1/3...不过,我希望有比这更好的解决方案。 - Rick Love
de Brujin tori的文章非常有帮助。 - Rick Love
与朴素解决方案相比,它将大小减小到1/3,即减少了2/3。 - j_random_hacker
好的,我需要为一个3x3网格构建一个de Brujin环面。从文章中已知结果不能是正方形,但它暗示着应该是可能的...接下来我将研究如何编写代码。 - Rick Love

2
下面的520位字符串包含所有3x3位模式作为连续子序列:
XXXXXXXXX.XXXXXXX..XXXXXX.X.XXXXXX...XXXXX.XX.XXXXX.X..XXXXX..X.XXXXX....XXXX.XXX.XXXX.XX..XXXX.X.X.XXXX.X...XXXX..XX.XXXX..X..XXXX...X.XXXX.....XXX.XXX..XXX.XX.X.XXX.XX...XXX.X.XX.XXX.X.X..XXX.X..X.XXX.X....XXX..XX..XXX..X.X.XXX..X...XXX...XX.XXX...X..XXX....X.XXX......XX.XX.XX.X..XX.XX..X.XX.XX....XX.X.XX..XX.X.X.X.XX.X.X...XX.X..X..XX.X...X.XX.X.....XX..XX...XX..X.X..XX..X..X.XX..X....XX...X.X.XX...X...XX....X..XX.....X.XX.......X.X.X.X..X.X.X....X.X..X...X.X...X..X.X......X..X..X.....X...X....X.........XXXXXXXX

或者,如果你喜欢,j_random_hacker的版本:
............X..X..X..X...........X..X..X..X...........X..X..X..X...........X..X..X..X.X..X..X..XX.XX.XX.XX.X..X..X..XX.XX.XX.XX.X..X..X..XX.XX.XX.XX.X..X..X..XX.XX.XX.XX.........X..X..X..X........X..X..X..X........X..X..X..X.X..X..XX.XX.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XX.XX.XX......X..X..X..X.....X..X..X..X.X..XX.XX.XX.XX.X..XX.XX.XX.XX.X..XX.XX.XX.XX.X..XX.XX.XX.XX...X..X..X..X.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..
......X..X........X..X.....X..X........X..X.X..XX.XX.X..X..XX.XX.X..XX.XX.X..X..XX.XX.....X..X........X..X.....X..X........X..X.X..XX.XX.X..X..XX.XX.X..XX.XX.X..X..XX.XX...X..X........X..X.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XX..X..X........X..X..X..X........X..X.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XXXXXXXX.XX.XXXXXXXXXXX.XX.XXXXXXX.XX..X..X.XX.XX.XX..X..X.XX.XXXXXX.XX.XXXXXXXXXXX.XX.XXXXXXXXX.XX.XXXXXXX..X..X.XX.XX..X..X.XX.XXX.XX.XXXXXXXX.XX.XXXXXX......X..X.....X..X.X..XX.XX.X..XX.XX...X..X.XX.XX.XX.XXXXXXXXXX..
...X.....X.....X.....X.XX.X..XX.X..XX.X..XX..X.....X.....X.....X.XX.X..XX.X..XX.X..XX..X.....X.....X.....X.XX.X..XX.X..XX.X..XX..X.....X.....X.....X.XX.X..XX.X..XX.X..XXXXX.XXXXX.XXXXX.XXXX..X.XX..X.XX..X.XXX.XXXXX.XXXXX.XXXX..X.XX..X.XX..X.XXX.XXXXX.XXXXX.XXXX..X.XX..X.XX..X.XXX.XXXXX.XXXXX.XXX...X.....X.....X.XX.X..XX.X..XX..X.....X.....X.XX.X..XX.X..XX..X.....X.....X.XX.X..XX.X..XXXXX.XXXXX.XXXX..X.XX..X.XXX.XXXXX.XXXX..X.XX..X.XXX.XXXXX.XXX...X.....X.XX.X..XX..X.....X.XX.X..XXXXX.XXXX..X.XXX.XXX...X.XXX..

或者您可以节省空间,仅使用从0到511的数字,对于大多数计算机来说,这些数字都是9位模式。


你使用了什么算法来获得这个值? - Rick Love
@RickLove 这个算法是 j_random_hacker 的想法。 - גלעד ברקן

0

"一个包含每种可能情况的紧凑网格是指定在每种情况下使用哪个瓷砖的最有效方法,并消除了所有冗余。"

我倾向于不同意。

无论您折叠练习的结果如何,将其索引以检索给定的3x3模式将需要8位索引,因为恰好有256个瓷砖邻接情况。如果您的紧凑表示包含超过256个模式-即混合了不需要或冗余的模式-则需要超过八位进行索引。

然而,一个8位字节已经可以表示所有可能的邻接情况,如果您将其视为位掩码并以某种方式将八个位映射到3x3网格的八个外部瓷砖上。这意味着折叠的主网格-德布鲁因风格或其他风格-是多余的,可以被取消。


我并不试图列出所有可能的索引值。正如你所说,每个可能的索引都是一个8位值。我将使用这个作为从每个索引到用于该索引的特定值的映射。我将通过在每种情况下将X更改为另一个字符来实现这一点。 - Rick Love
在这种情况下,一个字节查找表(置换)是最紧凑的简单数据结构,允许您指定从8位索引到8位位掩码(模式)的任意映射,包括任意置换。解决de Bruijn问题的方案只会给你一个固定的映射;除了f(i) = i之外,还有其他易于计算的固定映射/置换,如格雷码f(i) = (i >> 1) ^ i和许多其他映射。通常,从信息论(熵/编码)的角度看待事物往往是有帮助的;它解释了为什么即使是de Bruijn也无法击败香农。 - DarthGizka
1
@RickLove 我不明白你打算如何使用这个序列 - 你能举个例子说明一下你所谓的“索引”和“值”实际上是什么吗?为什么你不能简单地使用0到511之间的数字,它们都是9位模式呢? - גלעד ברקן
我的目的是全面地表达每个模式的结果:更新问题以进行演示。 - Rick Love

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接