http://en.wikipedia.org/wiki/De_Bruijn_torus
http://datagenetics.com/blog/october22013/index.html
我需要尽可能密集地组合一个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?
???
目的是对每种可能情况进行详尽的表达,以便得出结果。
实践中
我曾尝试过这样做,但发现结果太随机,无法很好地达到目标。作为人类,由于组织不当,在每种情况下选择正确的值是困难的。手动分组相似模式仍然更有效。