#include #define NO_DEBUG #ifdef DEBUG #define DEBUG_P1(S,A) printf(S,A) #define DEBUG_P2(S,A,B) printf(S,A,B) #define DEBUG_P3(S,A,B,C) printf(S,A,B,C) #define DEBUG_P4(S,A,B,C,D) printf(S,A,B,C,D) #define DEBUG_P6(S,A,B,C,D,E,F) printf(S,A,B,C,D,E,F) #else #define DEBUG_P1(S,A) #define DEBUG_P2(S,A,B) #define DEBUG_P3(S,A,B,C) #define DEBUG_P4(S,A,B,C,D) #define DEBUG_P6(S,A,B,C,D,E,F) #endif /* Finding minimal rulers. We would like to construct a set {p_1, p_2, ... p_k} such that { p_j - p_i | 0 <= i < j <= k } subset {1, 2, .. n} */ /* typing of search method: */ #define NO_L_LIM /* Limit l = p_k */ #define K_LIM /* Limit k */ #define ONLY_FIRST /* how many solutions should be printed */ /* maximum values for n, k, and l */ #define MAX_N 100 #define MAX_K MAX_N #define MAX_L (MAX_N+2) int g_n, g_k, g_l; /* = p_k */ int opt_print_sol; int nr_to_check; int ruler[MAX_N]; int found[MAX_L]; int found_at[MAX_K][MAX_L]; int sol_found; int count[MAX_L][MAX_K]; void check_solution(int k, int l) { int i; if (opt_print_sol == 2) { int j; #ifdef L_LIM printf("found k=%d: ", k + 2)); #else printf("found k=%d: ", k + 1); #endif for (j = 0; j <= k; j++) printf("%d ", ruler[j]); #ifdef L_LIM printf("%d ", g_l); #endif printf(" | "); for (j = 1; j <= g_n; j++) printf(" %d", found[j]); /* printf("\n"); */ } if (found[g_n+1] > 0) { if (opt_print_sol == 2) printf(" NOT TRUE\n"); return; /* not a true sparse ruler for n */ } /* Check if minimal */ for (i = 0; i <= k; i++) { int j, nn = 1; for (j = 1; j <= g_k && nn; j++) nn = found_at[i][j] < found[j]; if (nn) { if (opt_print_sol == 2) printf(" NOT MINIMAL FOR %d\n", i); return; } } #ifdef L_LIM { int j, nn = 1; for (j = 1; j <= g_k && nn; j++) nn = found_at[g_l][j] < found[j]; if (nn) { if (opt_print_sol == 2) printf(" NOT MINIMAL FOR %d\n", k+1); return; } } #endif if (opt_print_sol == 2) printf(" TRUE, MINIMAL\n"); if (opt_print_sol == 1) { int j; #ifdef L_LIM /* printf("found k=%d: ", k + 2); */ #else /* printf("found k=%d: ", k + 1); */ #endif for (j = 0; j <= k; j++) printf("%d ", ruler[j]); #ifdef L_LIM printf("%d ", g_l); #endif /* printf(" | "); for (j = 1; j <= g_n; j++) printf(" %d", found[j]); */ printf("\n"); } sol_found++; #ifdef L_LIM count[g_l][k + 2]++; #else count[l][k + 1]++; #endif } void fill (int k, int at, int till, int nr_to_find) { int i,j, v, new_nr_to_find; DEBUG_P6("%*sfill (%d, %d, %d, %d)\n", k, " ", k, at, till, nr_to_find); k++; till++; DEBUG_P3("%*snow k=%d: ", k, " ", k + 1); for (j = 0; j < k; j++) DEBUG_P1("%d ", ruler[j]); #ifdef L_LIM DEBUG_P1("%d", g_l); #endif DEBUG_P4("\n%*snr_to_find: %d, nr_to_check %d\n", k, " ", nr_to_find, nr_to_check); for (i = at; i < till && i <= at + g_n; i++) { ruler[k] = i; new_nr_to_find = nr_to_find; for (j = 0; j < k; j++) { v = i - ruler[j]; if (v <= g_n) { found_at[k][v]++; found_at[j][v]++; if (found[v]++ == 0) new_nr_to_find--; } else if (v == g_n + 1) found[v]++; } nr_to_check -= k; #ifdef L_LIM { v = g_l - i; if (v <= g_n) { found_at[k][v]++; found_at[g_l][v]++; if (found[v]++ == 0) new_nr_to_find--; else if (v == g_n + 1) found[v]++; } nr_to_check--; } #endif DEBUG_P3("%*sseek k=%d: ", k, " ", k + 1); for (j = 0; j <= k; j++) DEBUG_P1("%k ", ruler[j]); #ifdef L_LIM DEBUG_P1("%d", g_l); #endif DEBUG_P4("\n%*snr_to_find: %d, nr_to_check %d\n", k, " ", new_nr_to_find, nr_to_check); if (new_nr_to_find == 0) check_solution(k, i); else if ( found[g_n + 1] == 0 #ifdef K_LIM && new_nr_to_find <= nr_to_check #else && new_nr_to_find < nr_to_find #endif ) fill(k, i+1, till, new_nr_to_find); #ifdef ONLY_FIRST if (sol_found > 0) return; #endif for (j = 0; j < k; j++) { v = i - ruler[j]; if (v <= g_n) { found_at[k][v]--; found_at[j][v]--; found[v]--; } else if (v == g_n + 1) found[v]--; } nr_to_check += k; #ifdef L_LIM { v = g_l - i; if (v <= g_n) { found_at[k][v]--; found_at[g_l][v]--; found[v]--; } else if (v == g_n + 1) found[v]--; nr_to_check++; } #endif } } void solutions(int n, int k, int l, int table_form) { int i, j, nr_to_find, min_k; int not_found = 1; if (opt_print_sol) printf("finding solutions for k = %d and l = %d\n", k, l); ruler[0] = 0; ruler[k] = l; sol_found = 0; for (i = 0; i < MAX_L; i++) for (j = 0; j < MAX_K; j++) { count[i][j] = 0; found_at[j][i] = 0; } for (i = 0; i <= n; i++) found[i] = 0; nr_to_check = (k * (k - 1))/2; nr_to_find = n; #ifdef L_LIM { if (l <= n) { found[n]++; found_at[0][n]++; found_at[l][n]++; nr_to_find--; } nr_to_check--; } #endif g_n = n; g_k = n; g_l = l; #ifdef L_LIM fill(0, 1, l - k + 2, nr_to_find); #else fill(0, 1, l - k + 1, nr_to_find); #endif if (sol_found == 0) return; min_k = 2; while ((min_k*(min_k-1))/2 < n) min_k++; for (j = min_k; j < MAX_K; j++) { int found = 0; int im; for (im = MAX_L - 1; im >= n; im--) if (count[im][j] != 0L) { found = 1; break; } if (table_form && not_found && !found) printf("%3d |\n", j); if (found) { not_found = 0; if (table_form) printf("%3d |", j); else #ifdef K_LIM printf("%3d %3d k |", n, j); #else printf("%3d %3d |", n, j); #endif for (i = n; i <= im; i++) printf(table_form ? " %3d" : " %d", count[i][j]); printf("\n"); } } } void print_table(int n) { int k, i; opt_print_sol = 1; printf("

Number of true, minimal sparse rulers for length %d

" "\n\n
\n    |", n);
    for (i = n; i < n + 10; i++)
        printf(" %3d", i);
    printf("\n----+");
    for (i = n; i < n + 10; i++)
        printf("----");
    printf("\n");
   
    k = 2; 
    while ((k*(k-1))/2 < n)
        k++;

    /* solutions(n, k, MAX_L, 1); */
    solutions(n, k, MAX_L, 1);
/*    if (sol_found == 0) 
    {   k++;
        solutions(n, k, MAX_L, 1);
    } */
/*
    while (sol_found != 0)
    {   k++;
        solutions(n, k, MAX_L, 1);
    }
*/
    printf("
\n\n"); } void main() { int n = 20; int k = 2; opt_print_sol = 1; print_table(37); #ifdef COMMENT for (n = 5; n < 6; n++) { while ((k*(k-1))/2 < n) k++; DEBUG_P4("n = %d, k = %d (%d), l = %d\n", n, k, (k*(k-1))/2, n); solutions(n, k, n, 1, 1); solutions(n, k+1, n, 1, 1); /* Does not work correct */ solutions(n, k, MAX_L, 0, 1); /* if (sol_found == 0) solutions(n, k+1, MAX_L, 0, 1); */ /* solutions(n, k, MAX_L, 0, 0); */ } #endif }