如何利用预计算查找表实现多格骨牌（Polyomino）的一一映射？

本周早些时候，我询问了如何加速判断bitboard中是否包含polyomino的方法。我对polyomino的定义是所有方块通过边相连的任意排列，不会因存在镜像、旋转或翻转版本，或带有孔洞而排除。有用户指出，使用查找表统计0岛数量可实现更快判断（多数人统计1岛，但我的现有逻辑使用0岛）。

经过一番研究后我思考：能否直接使用该查找表？例如输入100，返回第100个polyomino。目前我通过遍历每个ulong并逐一检查来查找目标，而polyomino之间的间隔可能极大，最大约为4×10¹⁸。因此我希望跳过无需关注的内容，仅聚焦于polyomino。我已在评论中询问该用户，对方表示可行，因此发布此帖，欢迎任何人解答。

以下是上一篇帖子中用于创建查找表的代码：

/// <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));
}

内容的提问来源于stack exchange，提问作者timeslidr