أكبر مجموعة من الأرقام المكونة من 10 أرقام حيث لا توجد مسافة هامينج = 1 مع أي أرقام أخرى

Question

أنا أعمل على نظام يتطلب إدخال بيانات يدويا لأرقام مكونة من 10 أرقام (= = 0123456789).للمساعدة في منع أخطاء البيانات ، أريد تجنب توليد أي سلسلتين التي لديها مسافة هامينغ من 1.

على سبيل المثال ، إذا قمت بإنشاء السلسلة 0123456789 ، فلن أرغب أبدا في إنشاء أي من هذه السلاسل:{1123456789, 2123456789, 3123456789, ...}

ما هي أكبر مجموعة من سلاسل فريدة من نوعها في الكون من السلاسل الممكنة التي تلبي القيد حيث لا سلسلتين لديها مسافة هامينغ من 1?إذا كان من الممكن تحديد هذه المجموعة, هل هناك أي طريقة معقولة لتعداد ذلك?

Answer 1

هناك حل بسيط:استخدم بالضبط السلاسل التي تكون فيها مبالغ الأرقام قابلة للقسمة على $10$.هناك $10^9$ هذه السلاسل وأنه من السهل تعداد لهم ، والعثور على $i$- عشر منهم في ترتيب معجمي ، وتوليد عشوائية مثل هذه السلسلة ، وهلم جرا.

في الواقع ، إذا اختلفت سلسلتان في موضع واحد بالضبط، فإن مجموع أرقامهما يكون أيضا مودولو مختلفا $10$.على سبيل المثال ، مجموع الأرقام للسلاسل $0123456789$, $1123456789$, ld \ لدوتس$, $9123456789$ هي $45$, $46$, ld \ لدوتس$, $54$ على التوالي.

علاوة على ذلك ، هذا الحل هو أكبر قدر ممكن.في الواقع ، هناك $10^9$ هذه السلاسل:لكل طريقة للاختيار أولا $9$ الأرقام ، هناك طريقة واحدة بالضبط لاختيار الرقم الأخير لجعل المجموع قابلا للقسمة على $10$.وبالتالي ، هناك $10^9$ سلاسل في مجموعة لدينا.

من ناحية أخرى, أي مجموعة من السلاسل مع الحد الأدنى من المسافة هامينغ $2$ لديه على الأكثر $10^9$ عناصر.في الواقع ، ضع في اعتبارك $10$ سلاسل مع بادئة معينة من الطول $9$.انهم جميعا على مسافة هامينغ $1$ بعضها البعض (لأنها تختلف فقط في الموضع الأخير).وبالتالي ، يمكن أن ينتمي واحد منهم على الأكثر إلى أي مجموعة "جيدة".لذلك ، تحتوي أي مجموعة "جيدة" على الأكثر $10^9$ عناصر.