Costas Array Problem

algorithm

コスタス配列問題、というのを知った。

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


どこまで高速にできるようになるかな。