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