距離がハミング距離を持つ10桁の数字の最大セット= 1

Question

私は10桁の数字の手動データ入力を必要とするシステムに取り組んでいます（Σ= 0123456789）。データエラーを防ぐために、ハミング距離が1の2つの文字列を生成しないようにしたい。

たとえば、文字列0123456789を生成すると、これらの文字列を生成したくない場合は、次のいずれかの文字列を生成したくありません。{1123456789,2123456789,3123456789、...}

2つの文字列がハミング距離が1でない制約を満たす制約を満たす可能性のある文字列の宇宙の最大の一連の文字列とは何ですか？このセットを識別できる場合は、それを列挙する合理的な方法はありますか？

Answer 1

単純な解決策はあります。 $ 10 $ によって分割されている数字の合計で文字列を正確に使用します。 $ 10 ^ 9 $ があり、それらを列挙するのは簡単です。 $ i $ -th辞書順序でのそれらのうち、そのような弦、et cetera。

確かに、2つの文字列が正確に1つずつ異なる場合、それらの数字の合計も異なる $ 10 $ です。たとえば、文字列の数字の合計 $ 0123456789 $ 、 $ \ ldots $ 、 $ 9123456789 $ $ 45 $ 、 $ 46 $ 、 $ \ ldots $ 、 $ 54 $ 。

また、この解決策は可能な限り大きい。確かに、 $ 10 ^ 9 $ があります。 $ 9 $ 数字を選択するたびに $ 10 $ によって分割されるための最後の数字を選択するための正確に1つの方法です。したがって、 $ 10 ^ 9 $ 文字列の文字列。

任意のの任意ののセット $ 2 $ が $ 10 ^ 9 $ 要素。実際、長さ $ 9 $ の指定されたプレフィックスを持つ文字列を考慮してください。それらはすべてハミング距離 $ 1 $ の範囲内です（最後の位置でのみ異なるため）。したがって、それらのうちの1つは「良い」セットに属することができます。したがって、任意の "good" setが $ 10 ^ 9 $ 要素を含みます。