3
$\begingroup$

I'm working on a system that will require manual data entry of 10-digit numbers (Σ = 0123456789). To help prevent data errors, I want to avoid generating any two strings that have a hamming distance of 1.

For example, if I generate the string 0123456789 then I never want to generate any of these strings: {1123456789, 2123456789, 3123456789, ...}

What is the largest set of unique strings in the universe of possible strings that satisfy the constraint where no two strings have a hamming distance of 1? If this set can be identified, is there any reasonable way to enumerate it?

$\endgroup$
2
  • 2
    $\begingroup$ Such a set is known as a code with minimal distance 2. We usually like codes over finite fields, but unfortunately there is no finite field of size 10. That's why ISBN uses an eleventh symbol, X. $\endgroup$ – Yuval Filmus Jul 10 '20 at 4:53
  • $\begingroup$ @Yuval Filmus: well, in this exact case, we don't really need finite fields or any other complicated constructions, because "adding a parity bit" (only now "the parity bit" can take $10$ values) is enough. $\endgroup$ – Kaban-5 Jul 13 '20 at 17:41
3
+50
$\begingroup$

There is a simple solution: use exactly the strings with sums of digits being divisible by $10$. There are $10^9$ such strings and it is easy to enumerate them, find $i$-th of them in the lexicographic order, generate random such string, et cetera.

Indeed, if two strings differ in exactly one position, then their sums of digits are also different modulo $10$. For example, the sums of digits for strings $0123456789$, $1123456789$, $\ldots$, $9123456789$ are $45$, $46$, $\ldots$, $54$ respectively.

Moreover, this solution is largest possible. Indeed, there are $10^9$ such strings: for every way to choose first $9$ digits, there is an exactly one way to choose the last digit to make the sum divisible by $10$. Hence, there are $10^9$ strings in our set.

On the other hand, any set of strings with minimal Hamming distance $2$ has at most $10^9$ elements. Indeed, consider $10$ strings with a given prefix of length $9$. They all are within Hamming distance $1$ of each other (because they differ only in the last position). Hence, at most one of them can belong to any "good" set. Therefore, any "good" set contains at most $10^9$ elements.

$\endgroup$
1
  • $\begingroup$ This is a lovely result, thank you! It was not obvious to me. I will award the bounty when I am able. $\endgroup$ – Nic Jul 13 '20 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.