Größter Satz von 10-stelligen Zahlen, in denen keine Hamming-Entfernung aufweist= 1 mit einem anderen
-
29-09-2020 - |
Frage
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?
Lösung
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
Auf der anderen Seite, beliebiger -Set von Saiten mit minimalem Hamming-Abstand