Costas Array Problem
コスタス配列問題、というのを知った。
https://en.wikipedia.org/wiki/Costas_array
「A review of Costas arrays」
http://www.hindawi.com/journals/jam/2006/026385/abs/
コスタス配列とは
サイズNのコスタス配列とは、長さがNの配列 f であって、以下の条件を満たすものをいう。
- f は [0, 1, ..., N-1] のpermutationである
D_l = { f[i + l] - f[i] | 0 <= i < N - l }
としたとき、D_l
の要素はdistinctである、が全てのl(1 <= l < N)
で成立する
たとえば、N=4としたとき、
- f = {0, 1, 3, 2} はコスタス配列
- f = {2, 0, 3, 1} は D_1 = {-2, 3, -2} なのでコスタス配列ではない
コスタス配列であるための条件を幾何的に表すと、
「N*Nの二次元グリッド上にN個の点を配置する。どの行にもどの列にも点は1つ。点から点へのベクトル(N(N-1)/2個ある)を考えたとき、すべてのベクトルは互いに異なる」
ということになる。
上記のN=4の例をそれぞれグリッド的に書くと次のようになる、
コスタス配列 ■□□□ □■□□ □□□■ □□■□ コスタス配列でない □□■□ ■□□□ □□□■ □■□□
コスタス配列を列挙する
これまでのところ、N<=29 のコスタス配列が全列挙されている。
N=29 が計算されたのは2011年。CPU時間366.55年分、実時間230日かけたそうな。
「Results of the enumeration of Costas arrays of order 29」
http://www.aimsciences.org/journals/displayArticlesnew.jsp?paperID=6376
列挙のために使った手法は、N=28 を全列挙した論文にいろいろ書かれているみたい(まだ読んでない)。
http://eeme.ucd.ie/~kdrakaka/work/publications/047.The_Enumeration_of_Costas_Arrays_of_Order_28_and_Its_Consequences.pdf
Nごとのコスタス配列の個数を表す数列は、OEISにある。
https://oeis.org/A008404
この分野の大家だったらしい Konstantinos Drakakis 氏のサイト
http://eeme.ucd.ie/~kdrakaka/indexen.htm
(2011年以降は研究から引退して金融ビジネスやってるっぽい)
問題
未解決な問題がいろいろある。
「Open Problems in Costas Arrays」
http://arxiv.org/pdf/1102.5727.pdf
一番わかりやすいのが、「サイズNのコスタス配列の数を C(N) としたとき、すべてのNで C(N) > 0 か?」。
現在、コスタス配列が存在するかどうか確かめられていない最小のNは32。
2014年に東大で「スパコン24時間回したら N=32 で1つくらい見つかるんじゃないの」ということで試したが、見つからなかったとのこと。
http://www.cc.u-tokyo.ac.jp/support/press/news/VOL17/No1/11_201501hpc-2.pdf
N=素数-1 とか N=素数の累乗-2 とか、特定のNについてはコスタス配列を生成するアルゴリズムがある。
知られているアルゴリズムによって生成できないCostas Arrayは、"sporadic" と呼ばれて珍重(?)されている。
OEISにある C(N) の数列を見てみるとだんだん小さくなっているので、C(N) は0に近づきそうな気もするが、
C(N) のオーダーについて分かっているのは、C(N)/N! = O(1/N)
であることくらいらしい。
実装してみた
自分でも、コスタス配列を列挙するプログラムを簡単に作ってみた。
まず、ナイーブに N! 通りのpermutationを作ってそれぞれ条件をチェックする方法だと、手元で実行する気になるのはN=13くらいまで(実行環境は Macbook Air 2012 2.0GHz Core i7)。
https://github.com/tomerun/CostasArray/blob/c277f15da4591ac9e685dcd0fcd509d67cdd0e8e/main.cpp
$ time ./solver 10 ans_count:2160 real 0m0.172s user 0m0.166s sys 0m0.003s $ time ./solver 11 ans_count:4368 real 0m2.286s user 0m2.282s sys 0m0.003s $ time ./solver 12 ans_count:7852 real 0m31.387s user 0m31.292s sys 0m0.032s $ time ./solver 13 ans_count:12828 real 7m2.614s user 7m1.114s sys 0m0.513s
自明な枝刈り(permutationを作る途中で都度条件チェックしてviolateしたら枝刈り)を足すと、N=15くらいまではいける。
https://github.com/tomerun/CostasArray/blob/2db147b220e9e68436e26b4cb862993b2c3b91ef/main.cpp
$ time ./solver 10 ans_count:2160 real 0m0.034s user 0m0.026s sys 0m0.003s $ time ./solver 11 ans_count:4368 real 0m0.143s user 0m0.138s sys 0m0.003s $ time ./solver 12 ans_count:7852 real 0m0.781s user 0m0.776s sys 0m0.003s $ time ./solver 13 ans_count:12828 real 0m4.223s user 0m4.213s sys 0m0.008s $ time ./solver 14 ans_count:17252 real 0m22.039s user 0m22.014s sys 0m0.016s $ time ./solver 15 ans_count:19612 real 2m0.588s user 2m0.299s sys 0m0.113s
どこまで高速にできるようになるかな。