Hatena::ブログ(Diary)

当面C#と.NETな記録 このページをアンテナに追加 RSSフィード

2009/7/15 (水)

[] De Bruijn sequence を列挙するコード  De Bruijn sequence を列挙するコードを含むブックマーク  De Bruijn sequence を列挙するコードのブックマークコメント

いろいろとコメントをいただいているうちに De Bruijn sequence がわかってきました。初めは数学的な背景には興味がなかったんだけど、De Bruijn sequence をすべて列挙する問題が最近遊んでいるデータマイニングの頻出集合を求める問題とそっくりなことに気づいて、ちょっと練習がてらコードを書いてみました。かのダイクストラもコード書いて遊んでみたんなら自分もちょっと遊んでみようかなと。求めてどうするかは知りませんw

De Bruijn sequence の詳しい説明はこちら

http://chessprogramming.wikispaces.com/De+Bruijn+sequence

深さ優先探索をする再帰によるバックトラックの簡単なコードです。De Bruijn sequence は爆発的な勢いで解の数が増えていくので小さい数字で動かしてみてください。解の数は |B(2,5)|=2048、|B(2,6)|=67,108,864、|B(2,7)|=144,115,188,075,855,872 といった具合に増えていきます。大きい数字だとメモリが尽きるかも。B(9,1) だと |B(9,1)|=40320 だけど、B(9,2) になると |B(9,2)|=1.347e+48 にもなります…。

De Bruijn sequence B(k,n) の先頭が n 個の 0 ではじまるのは、周期的な数列なのでずらしてできる値を同じものとみなしているようです。たとえば、B(2,2) は 0011 をずらせば 0110, 1100, 1001 が見つかります。B(k,1) は単なる順列です。

using System;
using System.Collections.Generic;
using System.Linq;

namespace SearchDeBruijnSequence
{
    public class SearchDeBruijnSequence
    {
        private readonly int k, n, max;
        private List<string> results = new List<string>();

        public SearchDeBruijnSequence( int k, int n )
        {
            if ( k < 2 || 10 < k )
                throw new ArgumentOutOfRangeException( "k" );
            if ( n < 1 )
                throw new ArgumentOutOfRangeException( "n" );

            this.k = k;
            this.n = n;
            double pow = Math.Pow( k, n );
            if ( ( double ) int.MaxValue < pow )
                throw new ArgumentOutOfRangeException( "k, n" );

            this.max = ( int ) pow;
        }

        public List<string> Search()
        {
            int[] array = new int[ this.max + this.n - 1 ];
            //SearchCore( array, -1 ); // 0 始まり以外の変形も列挙したければこちら
            SearchCore( array, this.n - 1 );
            return this.results;
        }

        private void SearchCore( int[] array, int tail )
        {
            // 重複?
            if ( !IsUnique( array, tail ) )
                return;

            // 完成?
            if ( IsComplete( array, tail ) )
            {
                Output( array );
                return;
            }

            // 次の反復へ
            for ( int i = 0; i < this.k; i++ )
            {
                array[ tail + 1 ] = i;
                SearchCore( array, tail + 1 );
            }
        }

        private bool IsUnique( int[] array, int tail )
        {
            if ( tail < this.n ) return true;

            int pos = tail - this.n + 1;
            int[] last = array.Skip( pos ).Take( this.n ).ToArray();

            for ( int i = 0; i < pos; i++ )
            {
                if ( array.Skip( i ).Take( this.n ).SequenceEqual( last ) )
                    return false;
            }
            return true;
        }

        private bool IsComplete( int[] array, int tail )
        {
            if ( tail != this.max - 1 ) return false;

            for ( int i = 0; i < this.n - 1; i++ )
            {
                array[ tail + 1 + i ] = array[ i ];
                if ( !IsUnique( array, tail + 1 + i ) )
                    return false;
            }
            return true;
        }

        private void Output( int[] array )
        {
            string str = string.Join( "",
                array.Take( this.max ).Select( m => m.ToString() ).ToArray() );
            this.results.Add( str );

            if ( ( this.max <= 64 && this.k == 2 )
                || ( this.n == 1 && this.k == 8 ) )
            {
                ulong x = Convert.ToUInt64( str, this.k );
                Console.WriteLine( "{0} : {1}", str, x );
            }
            else
            {
                Console.WriteLine( str );
            }
        }


        static void Main()
        {
            var searcher = new SearchDeBruijnSequence( 2, 4 );
            var result = searcher.Search();

            Console.WriteLine();
            Console.WriteLine( result.Count );

            Console.ReadKey();
        }
    }
}

ダイクストラのコードよりわかりやすい?

解の例。

B(2,1)
01 : 1

B(2,2)
0011 : 3

B(2,3)
00010111 : 23
00011101 : 29

B(2,4)
0000100110101111 : 2479
0000100111101011 : 2539
0000101001101111 : 2671
0000101001111011 : 2683
0000101100111101 : 2877
0000101101001111 : 2895
0000101111001101 : 3021
0000101111010011 : 3027
0000110010111101 : 3261
0000110100101111 : 3375
0000110101111001 : 3449
0000110111100101 : 3557
0000111100101101 : 3885
0000111101001011 : 3915
0000111101011001 : 3929
0000111101100101 : 3941

B(3,1)
012
021

B(3,2)
001021122
001022112
001102122
001102212
001120221
001121022
001122021
001122102
001202211
001211022
001220211
001221102
002011221
002012211
002101122
002110122
002112201
002122011
002201121
002201211
002210112
002211012
002211201
002212011
トラックバック - http://d.hatena.ne.jp/siokoshou/20090715
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 09 | 11 | 12 |
2007 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 08 | 09 | 10 | 12 |
2009 | 01 | 03 | 04 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 07 |
2011 | 04 | 07 | 10 |
2012 | 04 | 12 |
2013 | 08 |
2014 | 03 | 08 |
2017 | 09 |