Самый большой набор 10-значных чисел, ни одно из которых не имеет расстояния Хэмминга = 1 с любым другим

Question

Я работаю над системой, которая потребует ручного ввода 10-значных чисел (Σ = 0123456789).Чтобы предотвратить ошибки в данных, я хочу избегать генерации любых двух строк с расстоянием Хэмминга, равным 1.

Например, если я сгенерирую строку 0123456789, то я никогда не захочу генерировать ни одну из этих строк:{1123456789, 2123456789, 3123456789, ...}

Каков самый большой набор уникальных строк во вселенной возможных строк, удовлетворяющих ограничению, при котором никакие две строки не имеют расстояния Хэмминга, равного 1?Если этот набор можно идентифицировать, есть ли какой-нибудь разумный способ его перечисления?

Answer 1

Есть простое решение:используйте именно те строки, суммы цифр в которых делятся на $10$.Есть такие $10^9$ такие строки и их легко перечислить, найти $я$-расположите их в лексикографическом порядке, сгенерируйте случайную такую строку и так далее.

Действительно, если две строки отличаются ровно на одну позицию, то их суммы цифр также различаются по модулю $10$.Например, суммы цифр для строк $0123456789$, $1123456789$, $\ldots$, $9123456789$ являются $45$, $46$, $\ldots$, $54$ соответственно.

Более того, это максимально возможное решение.Действительно, существуют $10^9$ такие строки:для каждого способа нужно выбирать первым $9$ цифры, есть ровно один способ выбрать последнюю цифру, чтобы сумма была кратна $10$.Следовательно, существуют $10^9$ струны в нашем наборе.

С другой стороны, Любой набор струн с минимальным расстоянием Хэмминга $2$ имеет не более $10^9$ элементы.Действительно, рассмотрим $10$ строки с заданным префиксом длины $9$.Все они находятся на расстоянии Хэмминга $1$ друг друга (потому что они отличаются только последней позицией).Следовательно, не более одного из них может принадлежать к любому "хорошему" набору.Следовательно, любой "хороший" набор содержит не более $10^9$ элементы.