Optimal Golomb Rulerを探す

Optimal Golomb Ruler(OGR)とは、Golomb Rulerの内もっとも短いものの事です。Golomb Rulerとはn個の数字からなる数列GR-nにおいて、任意の要素a,b,c,d(ただしa>b、c>d、a≠b、c≠d)がa-b≠c-dを満たすものを言います。nの事をマーク数と呼ぶこともあります。

GR-nは全ての要素を自然数倍しても関係が壊れないため、無限に存在します。その内、数列の要素の最大値が最も小さいものをOGR-nとします。GRは反転しても関係が壊れないため、OGR-nは常に偶数個存在することになります。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int check_ruler( int mark_count, int *ruler );
void print_ruler( int mark_count, int *ruler );


int main( int ac, char *av[] )
{
    int mark, mark_count, *ruler, length, found, nodes;

    /* コマンドラインからマーク数を決定する */
    if( ac < 2 )
        return;
    mark_count = strtol( av[1], NULL, 10 );
    if( mark_count < 2 )
        mark_count = 2;

    /* ruler用配列を確保する */
    ruler = calloc( mark_count, sizeof(int) );
    if( ruler == NULL )
        return;

    /* ループ変数を初期化する */
    length = mark_count - 1;
    found = 0;
    nodes = 0;

    /* OGR探索ループ */
    while( found == 0 ) {
        /* rulerを0,1,2...,lengthで初期化する */
        for( mark = 1; mark < mark_count - 1; mark++ )
            ruler[mark] = mark;
        ruler[mark_count - 1] = length;

        /* 長さがlengthのGRを探す */
        while( 1 ) {
            /* 計算回数をカウント */
            nodes++;

            /* golomb rulerであるか */
            if( check_ruler( mark_count, ruler ) == 1 ) {
                print_ruler( mark_count, ruler );
                found = 1;
            }

            /* markを一つ先に進める */
            for( mark = mark_count - 2; mark > 0; mark-- ) {
                if( ruler[mark] < length - ( mark_count - mark - 1 ) ) {
                    ruler[mark]++;
                    for( mark = mark + 1; mark < mark_count - 1; mark++ )
                        ruler[mark] = ruler[mark - 1] + 1;
                    break;
                }
            }
            /* 進めるマークが無ければ終了 */
            if( mark == 0 )
                break;
        }
        /* lengthを増やす */
        length++;
    }

    /* 計算回数を表示 */
    printf( "%d nodes\n", nodes );
}


/* golomb ruler判定 */
int check_ruler( int mark_count, int *ruler )
{
    int n1, n2, n3, n4;

    for( n1 = 0; n1 < mark_count - 1; n1++ ) {
        for( n2 = n1 + 1; n2 < mark_count; n2++ ) {
            for( n3 = 0; n3 < mark_count - 1; n3++ ) {
                if( n1 == n3 )
                    continue;
                for( n4 = n3 + 1; n4 < mark_count; n4++ ) {
                    if( n2 == n4 )
                        continue;
                    /* 差の等しい要素の組があれば偽 */
                    if( ruler[n2] - ruler[n1] == ruler[n4] - ruler[n3] )
                        return( 0 );
                }
            }
        }
    }

    return( 1 );
}


/* ruler表示 */
void print_ruler( int mark_count, int *ruler )
{
    int mark;

    for( mark = 0; mark < mark_count; mark++ ) {
        printf( "%d", ruler[mark] );
        if( mark != mark_count - 1 )
            printf( "-" );
    }
    printf( "\n" );
}

定義に従い、Rulerを短いものから順に長くしていきながら全ての数列をGRとなるか試しています。当然ながらマーク数が多くなるほど計算に時間がかかり、現在のところOGR-11までしか求められていません。その結果は以下のとおりです。

OGR-4	0-1-4-6 0-2-5-6
OGR-5	0-1-4-9-11 0-2-7-8-11 0-2-7-10-11 0-3-4-9-11
OGR-6	0-1-4-10-12-17 0-1-4-10-15-17 0-1-8-11-13-17 0-1-8-12-14-17 0-2-7-13-16-17 0-3-5-9-16-17 0-4-6-9-16-17 0-5-7-13-16-17
OGR-7	0-1-4-10-18-23-25 0-1-7-11-20-23-25 0-1-11-16-19-23-25 0-2-3-10-16-21-25 0-2-5-14-18-24-25 0-2-6-9-14-24-25 0-2-7-13-21-22-25 0-2-7-15-21-24-25 0-3-4-12-18-23-25 0-4-9-15-22-23-25
OGR-8	0-1-4-9-15-22-32-34 0-2-12-19-25-30-33-34
OGR-9	0-1-5-12-25-27-35-41-44 0-3-9-17-19-32-39-43-44
OGR-10	0-1-6-10-23-26-34-41-53-55 0-2-14-21-29-32-45-49-54-55
OGR-11	0-1-4-13-28-33-47-54-64-70-72 0-1-9-19-24-31-52-56-58-69-72 0-2-8-18-25-39-44-59-68-71-72 0-3-14-16-20-41-48-53-63-71-72

世界では、OGR-23まで既に求められているそうです。また、OGRでは無いかもしれないが、ほぼOGRと思われる近似解はGR-150まで求められているそうです。