El mayor conjunto de números de 10 dígitos donde ninguno tiene la distancia de la habla= 1 con cualquier otra

Question

Estoy trabajando en un sistema que requerirá una entrada de datos manual de números de 10 dígitos (σ= 0123456789).Para ayudar a prevenir errores de datos, quiero evitar la generación de dos cadenas que tengan una distancia de hamaming de 1.

Por ejemplo, si genero la cadena 0123456789, entonces nunca quiero generar ninguna de estas cadenas: {1123456789, 2123456789, 3123456789, ...}

¿Cuál es el conjunto más grande de cadenas únicas en el universo de posibles cadenas que satisfacen la restricción en la que no tiene dos cuerdas una distancia de Hamming de 1?Si este conjunto se puede identificar, ¿existe alguna forma razonable de enumerarlo?

Answer 1

Hay una solución simple: use exactamente las cadenas con sumas de dígitos divisibles por $ 10 $ . Hay $ 10 ^ 9 $ tales cadenas y es fácil enumerarlos, encontrar $ i $ -th de ellos en el orden lexicográfico, genera aleatorio de tal cadena, etcétera.

De hecho, si dos cadenas difieren exactamente en una posición, entonces sus sumas de dígitos también son diferentes modulo $ 10 $ . Por ejemplo, las sumas de dígitos para cadenas $ 0123456789 $ , $ 1123456789 $ , $ \ ldots $ , $ 9123456789 $ son $ 45 $ , $ 46 $ , $ \ ldots $ , $ 54 $ respectivamente.

Además, esta solución es la mayor posible. De hecho, hay $ 10 ^ 9 $ dichas cadenas: por todas las maneras para elegir primero $ 9 $ dígitos, allí es exactamente una forma de elegir el último dígito para que la suma sea divisible por $ 10 $ . Por lo tanto, hay $ 10 ^ 9 $ cadenas en nuestro set.

Por otro lado, CUALQUIER Conjunto de cadenas con una distancia mínima de hamming $ 2 $ tiene en la mayoría de $ 10 ^ 9 $ elementos. De hecho, considere $ 10 $ cadenas con un prefijo dado de longitud $ 9 $ . Todos están dentro de la distancia de la distancia $ 1 $ entre sí (porque difieren solo en la última posición). Por lo tanto, a lo sumo, uno de ellos puede pertenecer a cualquier conjunto "bueno". Por lo tanto, cualquier conjunto "bueno" contiene en la mayoría de los elementos de $ 10 ^ 9 $ elementos.