在 C# 中查找第 N 个二进制回文数

引言

本文提供了一种使用 C# 代码中的一些数学方法来计算第 n 个二进制回文的方法。我觉得它很有用，因为我在 Google 上找到的所有方法都有不同的方法，并且依赖于预先计算到数组或使用蛮力迭代。

背景

该算法的基本思想是构造第 n 个回文，而不是检测它，而无需构造任何其他回文。

我所做的是将每个二进制回文分成左侧和右侧，因为一侧应该是另一侧的逆序。以下代码片段说明了这种划分。

---------------Initial Group------------
   0
   1

---------------Group 0------------------
  1|1

  101
  111

---------------Group 1------------------
 10|01
 11|11

 10001
 10101
 11011
 11111

---------------Group 2------------------
100|001
101|101
110|011
111|111

1000001
1001001
1010101
1011101
1100011
1101011
1110111
1111111

and so on ...

在上面的代码片段中，首先，连续的二进制回文按位数分组。在组 0 中，有 2 位和 3 位回文，在组 1 中，有 4 位和 5 位回文，依此类推。为了更好地可视化，我在偶数位回文的中间放置了“|”符号。

现在，如果我们忘记初始组和组 0，它们可以只是常量，我们可以开始考虑该算法。我们需要做的第一件事是计算我们的第 n 个元素将在哪个组中。在这里，二进制对数派上用场

groupIndex = floor(log2((nth / 3) + 1))

这里需要除以 3，因为我们的组可以分成 3 个子组

• 边之间没有数字 ('|' 符号用于说明)，
• 边之间有 '0'
• 边之间有 '1'

现在我们可以计算每个子组中的元素数量

subGroupCount = 2 ^ groupIndex

以及当前组之前的二进制回文的数量（使用几何级数的求和公式）

Sum = ((2 ^ groupIndex) - 1) * 3

让我们计算所需回文在其组内的索引

var insideGroupIndex = nth - Sum;

以及在子组内的索引

var insideSubGroupIndex = insideGroupIndex % subGroupCount;

现在我们可以确定我们的二进制回文在边之间是否没有数字、'0' 或 '1'（这是子组的索引）

var opType = (int)Math.Floor((double)insideGroupIndex / subGroupCount);

现在我们拥有组装回文的所有东西，但是我们必须为组内的 3 个子组中的每一个都这样做

• if (opType == 0) 二进制回文的左侧应该是 "1" + binaryStringRepresentation(subGroupIndex)，并在组中填充到数字计数。边之间不应该有连接器
• if (opType == 1) 二进制回文的左侧应该是 "1" + binaryStringRepresentation(subGroupIndex / 2)，并在组中填充到数字计数。连接器应该是 '0' 或 '1'，具体取决于 groupIndex 是否可被 2 整除（偶数或奇数）
• if (opType == 2) 二进制回文的左侧应该是 "1" + binaryStringRepresentation((subGroupIndex / 2) + (subGroupCount / 2))，并在组中填充到数字计数。连接器应该是 '0' 或 '1'，具体取决于 groupIndex 是否可被 2 整除（偶数或奇数）

最后，输出应该是

output = leftSide + connector + reverse(leftSide)

Using the Code

该算法的代码如下所示

private string GetNthBinaryPalindrome(int n)
{
    switch (n)
    {
        case 1:
            return "0";
        case 2:
            return "1";
        case 3:
            return "11";
        case 4:
            return "101";
        case 5:
            return "111";
        default:
            if (n < 1) 
                return null;
                
            var S = n - 3;
            var groupIndex = (int)Math.Floor(Math.Log((S / 3) + 1, 2));
            var digitsCount = group;
            var subGroupCount = (int)Math.Round(Math.Pow(2, group));
            var Sn = (subGroupCount - 1) * 3;
            var insideGroupIndex = S - Sn;
            var subGroupIndex = insideGroupIndex % subGroupCount;
            var opType = (int)Math.Floor((double)insideGroupIndex / subGroupCount);
            
            string leftSide;
            string connector;
            
            switch (opType)
            {
                case 0:
                    connector = "";
                    leftSide = "1" + 
                    Convert.ToString(subGroupIndex, 2).PadLeft(digitsCount, '0');
                    break;
                case 1:
                    connector = ((groupIndex & 1) == 0) ? "0" : "1";
                    leftSide = "1" + 
                    Convert.ToString(subGroupIndex / 2, 2).PadLeft(digitsCount, '0');
                    break;
                case 2:
                    connector = ((groupIndex & 1) == 0) ? "0" : "1";
                    leftSide = "1" + Convert.ToString(subGroupIndex / 2 + 
                    subGroupCount / 2, 2).PadLeft(digitsCount, '0');
                    break;
                default:
                    return null;
            }
            
            return String.Format("{0}{1}{2}", 
            leftSide, connector, String.Join("", leftSide.Reverse()));
    }
}

关注点

该算法可能可以进一步优化，但就我的目的而言，它已经足够高效了。

历史

• 2016 年 12 月 21 日：初始版本
• 2016 年 12 月 23 日：更正了回文列表组 1 中的错字