Set più grande di numeri a 10 cifre in cui nessuno ha la distanza di hamming= 1 con qualsiasi altro

Question

Sto lavorando su un sistema che richiederà l'immissione dei dati manuali di numeri a 10 cifre (Σ= 0123456789).Per aiutare a prevenire errori di dati, voglio evitare di generare due stringhe che hanno una distanza di hamming di 1.

Ad esempio, se generato la stringa 0123456789, non voglio mai generare nessuna di queste stringhe: {1123456789, 2123456789, 3123456789, ...}

Qual è la serie più grande di stringhe uniche nell'universo di possibili corde che soddisfano il vincolo in cui nessuna due stringhe ha una distanza di hamming di 1?Se questo set può essere identificato, c'è qualche modo ragionevole per enumerarlo?

Answer 1

C'è una soluzione semplice: utilizzare esattamente le stringhe con somme di cifre che sono divisibili da $ 10 $ . Ci sono $ 10 ^ 9 $ Tali stringhe ed è facile enumerarli, trovare $ I $ -h Di loro nell'ordine lessicografico, generare una stringa casuale, et cetera.

Infatti, se due stringhe differiscono esattamente in una posizione esattamente, le loro somme di cifre sono anche diverse moduli $ 10 $ . Ad esempio, le somme delle cifre per le stringhe $ 0123456789 $ , $ 1123456789 $ , $ \ Ldots $ , $ 9123456789 $ sono $ 45 $ , $ 46 $ , $ \ ldots $ , $ 54 $ rispettivamente.

Inoltre, questa soluzione è più grande possibile. Infatti, ci sono $ 10 ^ 9 $ Tali stringhe: per ogni modo per scegliere la prima classe $ 9 $ cifre, lì è esattamente un modo esattamente per scegliere l'ultima cifra per rendere la somma divisibile da $ 10 $ . Quindi, ci sono $ 10 ^ 9 $ stringhe nel nostro set.

D'altra parte, qualsiasi Set di stringhe con distanza di hamming minima $ 2 $ ha al massimo $ 10 ^ 9 $ elementi. Infatti, considerare $ 10 $ stringhe con un dato prefisso di lunghezza $ 9 $ . Sono tutti all'interno della distanza di hamming $ 1 $ dell'altro (perché differiscono solo nell'ultima posizione). Quindi, al massimo uno di loro può appartenere a qualsiasi set "buono". Pertanto, qualsiasi set "buono" contiene al massimo $ 10 ^ 9 $ elementi.