Größter Satz von 10-stelligen Zahlen, in denen keine Hamming-Entfernung aufweist= 1 mit einem anderen

Question

Ich arbeite an einem System, das eine manuelle Dateneingabe von 10-stelligen Nummern benötigt (σ= 0123456789).Um dabei zu helfen, Datenfehler zu vermeiden, möchte ich vermeiden, dass zwei Saiten erzeugt werden, die einen Hamming-Abstand von 1 haben.

Zum Beispiel, wenn ich die Zeichenfolge 0123456789 generiere, möchte ich niemals irgendeines dieser Saiten generieren: {1123456789, 2123456789, 3123456789, ...}

Was ist der größte Satz einzigartiger Saiten im Universum möglicher Saiten, die die Einschränkung erfüllen, in denen keine zwei Saiten einen Hamming-Abstand von 1 haben?Wenn dieses Set identifiziert werden kann, gibt es einen vernünftigen Weg, um ihn aufzulisten?

Answer 1

Es gibt eine einfache Lösung: Verwenden Sie genau die Saiten mit den Ziffernsummen, die von 10 $ $ teilbar sind. Es gibt 10 ^ 9 $ solche Saiten, und es ist einfach, sie aufzulisten, find $ i $ -th Von ihnen in der lexikographischen Reihenfolge, erwirtschaften Sie zufällig solcher String, et cetera.

in der Tat, wenn sich in genau einer Position zwei Saiten unterscheiden, sind ihre Ziffernsummen auch unterschiedlich modulo $ 10 $ . Zum Beispiel die Summen der Ziffern für Saiten $ 0123456789 $ , $ 1123456789 $ , $ \ ldots $ , $ 9123456789 $ sind $ 45 $ , $ 46 $ , $ \ ldots $ , $ 54 $ .

Darüber hinaus ist diese Lösung für den größtmöglichen möglich. In der Tat gibt es $ 10 ^ 9 $ solche Saiten: Für jede Möglichkeit, zuerst $ 9 $ Ziffern, dort ist genau eine Möglichkeit, die letzte Ziffer auszuwählen, um die Summe, die von $ 10 $ teilbar ist, auszuwählen. Daher gibt es $ 10 ^ 9 $ in unserem Set.

Auf der anderen Seite, beliebiger -Set von Saiten mit minimalem Hamming-Abstand $ 2 $ hat höchstens $ 10 ^ 9 $ Elemente. In der Tat, in Betracht ziehen $ 10 $ Saiten mit einem bestimmten Präfix von Länge $ 9 $ . Sie sind alle in der Hamming-Entfernung $ 1 $ voneinander (weil sie sich nur in der letzten Position unterscheiden). Daher können höchstens einer von ihnen zu jedem "guten" Set gehören. Daher enthält ein beliebiges "Gutes" -Set höchstens $ 10 ^ 9 $ Elemente.