Plus grande série de 10 chiffres où aucun n'a de Hamming Distance = 1 avec n'importe quel autre

Question

Je suis en train de travailler sur un système qui nécessitera la saisie manuelle des données de 10 chiffres (Σ = 0123456789).Pour aider à prévenir les erreurs de données, je veux éviter de générer de deux chaînes qui ont une distance de hamming de 1.

Par exemple, si je générer la chaîne de 0123456789 alors je ne veux plus jamais générer de l'une de ces chaînes:{1123456789, 2123456789, 3123456789, ...}

Ce qui est le plus grand ensemble de chaînes uniques dans l'univers de possible des chaînes de satisfaire la contrainte où aucun des deux chaînes ont une distance de hamming de 1?Si ce jeu peut être identifié, est-il un moyen raisonnable de les énumérer il?

Answer 1

Il existe une solution simple:utiliser exactement les cordes avec les sommes des chiffres étant divisible par $10$.Il y a $10^9$ ces chaînes et il est facile de les énumérer, trouver $i$-e d'entre eux dans l'ordre lexicographique, générer de l'aléatoire telle chaîne, et cetera.

En effet, si deux chaînes de caractères diffèrent exactement dans la même position, puis leurs sommes de chiffres sont également différents modulo $10$.Par exemple, la somme des chiffres pour les chaînes $0123456789$, $1123456789$, $\ldots$, $9123456789$ sont $45$, $46$, $\ldots$, $54$ respectivement.

De plus, cette solution est plus possible.En effet, il y a $10^9$ ces chaînes:pour tous les moyens de choisir en premier $9$ chiffres, il est exactement la façon de choisir le dernier chiffre de faire la somme divisible par $10$.Donc, il y a $10^9$ les chaînes de notre ensemble.

D'autre part, tout ensemble de chaînes avec un minimum de distance de Hamming $2$ a au plus $10^9$ éléments.En effet, considérer $10$ des chaînes de caractères avec un préfixe de longueur $9$.Ils sont tous à l'intérieur distance de Hamming $1$ les uns des autres (parce qu'ils ne diffèrent que dans la dernière position).Donc, à plus d'un d'entre eux peuvent appartenir à un "bon" jeu.Par conséquent, toute "bonne" set contient au plus $10^9$ éléments.