本周早些时候，我询问了如何加快检查位板是否包含多联骨牌的方法。一位用户表明，使用查找表可以更快地计算 0 岛的数量（我认为大多数人都使用 1，但我现有的很多逻辑都使用 0）。尝试了一段时间后，我开始思考：是否可以直接使用查找表？例如，如果我给它 100，它会给我第 100 个多联骨牌。因为现在我正在每个 ulong 上运行一个 for 循环并检查每个 ulong 直到找到我正在寻找的内容。多骨牌之间的差距可能非常大，最大的差距约为 4 万亿分之一。因此，最好跳过我不需要的内容，只关注多联骨牌。我在评论中询问了用户，他们说这是可能的，他们说是的，除非我误解了他们，所以我创建了这篇文章。当然，欢迎任何人回答。
这是上一篇文章中创建查找表的代码。
/// <summary>
/// Map from the long-form state code for each state to the state number
/// see expandState.
///
/// This is only used during state table construction.
/// </summary>
Dictionary<string, ushort> stateNumbers = new Dictionary<string, ushort>();
/// <summary>
/// Packed map from (state*256 + next_row_byte) -> transition
///
/// transition is next_state + (island_count<<12), where island_count is the
/// number of islands cut off from the further rows
/// </summary>
List<ushort> transitions = new List<ushort>();
/// <summary>
/// The byte representing a row of all water. Note that this code counts
/// 0-islands, not 1-islands
/// </summary>
const byte ALL_WATER = (byte)0xFF;
#region Disjoint Set
/*
* Disjoint set the proper way. The sets are integers in an array:
* For each integer i
* - i === 0 => set is uninitialized (not yet a set)
* - i < 0 => set is a link to ~i
* - i >= 0 => set is of size i
*/
// find with path compression.
int find(int[] sets, int s)
{
int parent = sets[s];
if (parent > 0)
{
return s;
}
else if (parent < 0)
{
parent = find(sets, ~parent);
sets[s] = ~parent;
return parent;
}
else
{
sets[s] = 1;
return s;
}
}
// union by size
bool union(int[] sets, int x, int y)
{
x = find(sets, x);
y = find(sets, y);
if (x == y)
{
return false;
}
int szx = sets[x];
int szy = sets[y];
if (szx < szy)
{
sets[y] += szx;
sets[x] = ~y;
}
else
{
sets[x] += szy;
sets[y] = ~x;
}
return true;
}
#endregion
/// <summary>
/// Expands the specified state code.
///
/// A state code is a string of digits.
/// 0 => water
/// x => island number x. new islands are numbered from left to right
/// </summary>
/// <param name="stateCode">The state code to expand.</param>
/// <param name="nextrow">the lower 8 bits represent the next row. 0-bits are land</param>
/// <returns>The transition code for the transition from stateCode to nextrow</returns>
ushort expandState(string stateCode, int nextrow)
{
// convert the next row into a disjoint set array
// if you want to count 1-islands instead of 0-islands, change `~nextrow` into `nextrow` below,
// and fix the ALL_WATER constant
int[] sets = new int[8];
for (int i = 0; i < 8; ++i)
{
sets[i] = (~nextrow >> i) & 1;
}
for (int i = 0; i < 7; ++i)
{
if (((~nextrow >> i) & 3) == 3)
{
union(sets, i, i + 1);
}
}
// map from state code island to first attached set in sets
int[] links = [-1, -1, -1, -1, -1, -1, -1, -1];
int topIslandCount = 0;
for (int i = 0; i < 8; ++i)
{
char digit = stateCode[i];
int topisland = digit - '1';
topIslandCount = Math.Max(topIslandCount, topisland + 1);
if (sets[i] != 0 && topisland >= 0)
{
// connection from prev row to nextrow
int bottomSet = links[topisland];
if (bottomSet < 0)
{
// this island is not yet connected
links[topisland] = i;
}
else
{
// the top island is already connected. union bottom sets
union(sets, bottomSet, i);
}
}
}
// count the number of top-row islands that don't connect to the next row.
int cutOffCount = 0;
for (int i = 0; i < topIslandCount; ++i)
{
if (links[i] < 0)
{
++cutOffCount;
}
}
// turn the new union-find array into a state code
char nextSet = '1';
char[] newChars = "00000000".ToCharArray();
for (int i = 0; i < 8; ++i)
{
links[i] = -1;
}
for (int i = 0; i < 8; ++i)
{
if (sets[i] != 0)
{
int set = find(sets, i);
int link = links[set];
if (link >= 0)
{
newChars[i] = newChars[link];
}
else
{
newChars[i] = nextSet++;
links[set] = i;
}
}
}
string newStateCode = new string(newChars);
// get the state number
if (stateNumbers.ContainsKey(newStateCode))
{
// state already exists and is/will be expanded
return (ushort)(stateNumbers[newStateCode] | (cutOffCount << 12));
}
ushort newState = (ushort)stateNumbers.Count;
stateNumbers.Add(newStateCode, newState);
// fill out the state table
while (transitions.Count <= (newState + 1) * 256)
{
transitions.Add(0);
}
for (int i = 0; i < 256; ++i)
{
transitions[newState * 256 + i] = expandState(newStateCode, i);
}
return (ushort)(newState | (cutOffCount << 12));
}
int startState = expandState("00000000", ALL_WATER);
Console.WriteLine(startState);
Console.WriteLine(stateNumbers.Count);
int Count0Islands(ulong bitboard)
{
int state = 0;
int count = 0;
for (int i = 0; i < 8; ++i)
{
var transition = transitions[state * 256 + (int)(bitboard & 0xFF)];
count += transition >> 12;
state = transition & 0xFFF;
bitboard >>= 8;
}
// transition to ALL_WATER to count last islands
count += transitions[state * 256 + ALL_WATER] >> 12;
return count;
}
ulong[] tests = {
0x7e220a7e4a58580Ful,
0x7e22087e4a58580Ful,
0xFFFFFFFFFFFFFFFFul,
0x813c425a5a423c81ul
};
foreach (ulong test in tests)
{
Console.WriteLine();
Console.WriteLine();
for (int row = 0; row < 8; ++row)
{
int rowByte = (int)(test >> (row * 8)) & 0xFF;
string rowStr = Convert.ToString(rowByte, 2).PadLeft(8, '0');
rowStr = rowStr.Replace("1", " ");
rowStr = rowStr.Replace("0", "#");
Console.WriteLine(rowStr);
}
Console.WriteLine();
Console.WriteLine("Islands: " + Count0Islands(test));
}
我上次为您制作的表格是一个有限状态转换器，它处理行位掩码并返回岛计数。
这并不完全是您所需要的。 为了生成第 N 个 Polymino 位板，我们需要：
如果我们从具有多项式数 N 的起始状态开始，我们可以沿着第 N 条路径下降到接受状态的 8 个转换。 然后可以使用这些转换上的 8 行位掩码来构造第 N 个多米诺。
您可以将以下内容添加到您/我现有的 FST 生成器中，以制作多米诺生成器表并生成多米诺。
这个表有点大，有 5126 个状态，652583 个转换，每个转换大约 16 个字节，所以大约 10MB。
/// <summary>
/// checker_state + next_row_number * 4096 + have_islands*65536 -> generator_state
/// </summary>
Dictionary<int, ushort> genStateNumbers = new Dictionary<int, ushort>();
/// <summary>
/// Generator states. These for a DFA that accepts all 8-row polyminoes.
/// State 0 is used as both the unique start state and the unique accept state
/// </summary>
List<List<GenTransitionInfo>> genStates = new List<List<GenTransitionInfo>>();
/// <summary>
/// Fill out a state in the generator table if it doesn't exist
/// Return the state number
/// </summary>
ushort makeGenState(int nextRowNumber, int checkerState, int haveIslands) {
int stateKey = checkerState + nextRowNumber * 4096 + haveIslands * 65536;
if (genStateNumbers.ContainsKey(stateKey)) {
return genStateNumbers[stateKey];
}
ushort newGenState = (ushort)genStates.Count;
genStateNumbers.Add(stateKey, newGenState);
var tlist = new List<GenTransitionInfo>();
genStates.Add(tlist);
int transitionsOffset = checkerState*256;
ulong totalPaths = 0;
for (int i = 0; i < 256; ++i) {
var transition = transitions[transitionsOffset + i];
int nextCheckerState = transition & 0x0FFF;
var newIslands = (transition >> 12) + haveIslands;
if (newIslands > (i == ALL_WATER ? 1 : 0)) {
// we are destined to get too many islands this way.
continue;
}
if (nextRowNumber == 7) {
// all transitions for row 7 have to to the accept state
// calculate total number of islands
newIslands += transitions[nextCheckerState * 256 + ALL_WATER] >> 12;
if (newIslands == 1) {
totalPaths += 1;
tlist.Add(new GenTransitionInfo { nextRow = (byte)i, nextState = 0, cumulativePaths = totalPaths });
}
} else {
ushort nextGenState = makeGenState(nextRowNumber + 1, nextCheckerState, newIslands);
ulong newPaths = genStates[nextGenState].LastOrDefault().cumulativePaths;
if (newPaths > 0) {
totalPaths += newPaths;
tlist.Add(new GenTransitionInfo { nextRow = (byte)i, nextState = nextGenState, cumulativePaths = totalPaths });
}
}
}
return newGenState;
}
// generate the DFA
makeGenState(0, startState, 0);
ulong TOTAL_POLYMINOES = genStates[0].LastOrDefault().cumulativePaths;
ulong getNthPolimyno(ulong n) {
int state = 0;
ulong poly = 0;
for (int row=0; row < 8; ++row) {
var tlist = genStates[state];
// binary search to find the transition that contains the nth path
int hi = tlist.Count - 1;
int lo = 0;
while (hi > lo) {
int test = (lo + hi) >> 1;
if (n >= tlist[test].cumulativePaths) {
// test is too low
lo = test + 1;
} else {
// test is high enough
hi = test;
}
}
if (lo > 1) {
n -= tlist[lo - 1].cumulativePaths;
}
var transition = tlist[lo];
poly = (poly<<8) | transition.nextRow;
state = transition.nextState;
}
return poly;
}
// TEST
Console.WriteLine("Total Polyminoes: " + TOTAL_POLYMINOES);
Console.WriteLine("Total Generator States: " + genStates.Count);
Console.WriteLine("Total Transitions: " + genStates.Sum(x => x.Count));
Random rand = new Random();
for (int i=0; i < 10; ++i) {
// Genterate a random ulong from 0 to TOTAL_POLYMINOES
ulong n = (ulong)rand.NextInt64((long) TOTAL_POLYMINOES);
ulong poly = getNthPolimyno(n);
Console.WriteLine();
Console.WriteLine("Polymino " + n + " is:");
for (int row = 0; row < 8; ++row)
{
int rowByte = (int)(poly >> (row * 8)) & 0xFF;
string rowStr = Convert.ToString(rowByte, 2).PadLeft(8, '0');
rowStr = rowStr.Replace("1", " ");
rowStr = rowStr.Replace("0", "#");
Console.WriteLine(rowStr);
}
}
struct GenTransitionInfo {
public byte nextRow;
public ushort nextState;
public ulong cumulativePaths;
}
包含测试代码，并产生如下输出：
Total Polyminoes: 51016818604894742
Total Generator States: 5126
Total Transitions: 652583
Polymino 42260088568217858 is:
#######
# #
# ####
######
# ####
#### ##
### #
# # #
Polymino 17307633173140022 is:
# # ####
##### #
# # # #
# # ####
####
# #
### ###
# #### #
请注意，总共有 51016818604894742 个不同的 64 位位板多米诺。 得到这个数字是我遇到这些麻烦的真正原因:)
您可以搜索这个号码，看看它以前出现在哪里！