De Bruijn列

De Bruijn列(ドゥブリュエイン列)はある文字または数字の集まりから指定長さの組み合わせを考える時に、それらの組み合わせを必ず一つ含む列. 例 "a,b"を使った3文字の組み合わせを考えると、"aaa","aab","aba","baa","bbb","bba","bab","abb"なので "aaababbbaa"がDe Bruijn列. この中に確かに(aaa, aab, aba, bab, abb, bbb, bba, baa)の8通り全て一度だけ含まれている

De Bruijn列の作り方は幾らかあるがここでは、 De Bruijnグラフを作成して、ハミルトニアン路を見つける方法を紹介. アルゴリズム ここではk文字("0","1"ならk=2)を使ってn文字("01011"ならn=5)の長さの組み合わせを作る場合を考える. 以下例は、2文字4文字の組み合わせを想定.下の図に対応. 1. まず(n-1)の組み合わせを列挙 000, 000, 001, 011, 111, 111, 110, 101, 011,110, 100, 001, 010, 101, 010, 100, 000. 2. これらをノードにしたDe bruijnグラフを作成. 3. このグラフを元に点を一度しか通らないハミルトニアン路を見つけ出す. 4. 見つけたハミルトニアン路に沿って文字列を集めると, (000 → 000 → 001→ 011→ 111→ 111→ 110→ 101→ 011→ 110→ 100→ 001→ 010→ 101→010→ 100→ 000) 5. 上記4.の数列の先頭の数字を集めていくとDe Bruijn列となる. DeBruijn列 : 0000111101100101000

Brute Force(総当たり攻撃)にて 仮に一度決定するごとに入力のし直しがないのならば(入力した末尾の文字列で判定. Enterキーを押さないなら)、入力回数を減らし、総当たり攻撃の効率を高めることができる. ほかには、「回転角度を示す符号」にするや「最上位の1が立っているビット」を見つける際などに役に立つ.