最大的10位数字设置，没有汉明距离= 1与任何其他

Question

我正在研究一个系统，需要手动数据输入10位数字（σ= 0123456789）。为了帮助防止数据错误，我想避免生成任何两个具有1的琴弦。

例如，如果我生成字符串0123456789，则我永远不想生成任何这些字符串：{1123456789,2123456789,3123456789，...}

宇宙中最大的独特弦集是满足约束的可能串的围兜，其中没有两个字符串的汉明距离为1？如果可以识别此集，是否有任何合理的方法来枚举它？

Answer 1

有一个简单的解决方案：使用与 $ 10 $ 可分离的数字的总和。有 $ 10 ^ 9 $ 这样的字符串，它很容易枚举它们，查找 $ i $ -th在词典顺序中，生成随机这样的字符串等。

事实上，如果两个字符串在恰好一个位置不同，那么它们的数字总和也是不同的modulo $ 10 $ 。例如，字符串 $ 0123456789 $ ， $ 1123456789 $ ， $ \ ldots $ ， $ 9123456789 $ 是 $ 45 $ ， $ 46 $ ， $ \ ldots $ ， $ 54 $ 。

此外，该解决方案是最大的。实际上，有 $ 10 ^ 9 $ 这样的字符串：为各种方式选择First $ 9 $ 数字是选择最后一位数字的一种方法，使得 $ 10 $ 。因此，我们集合有 $ 10 ^ 9 $ 字符串。

另一方面，任何字符串，最小汉明距离 $ 2 $ 具有最多 $ 10 ^ 9 $ 元素。实际上，考虑 $ 10 $ 字符串，具有给定的长度 $ 9 $ 。它们都在汉明距离 $ 1 $ 彼此之内（因为它们仅在最后一个位置不同）。因此，最多一个可以属于任何“好”集。因此，任何“良好”设置包含至多大多数<跨度类=“math-container”> $ 10 ^ 9 $ 元素。