1/* Exhaustive boundary minimisation for P(n,k) (Stage 5 robustness check).2 *3 * For every p in [p_lo, p_hi] enumerates ALL p-subsets X of V(P(n,k))4 * (no symmetry reduction, no SAT) and tabulates the distribution of5 * |dX| = |N[X] \ X|. Output per p: beta_p(n) = min |dX| and the histogram.6 * Independent of code/sat_or_ilp_solver.py (Lemma 3.4 / F(n,p)).7 *8 * usage: beta_brute n k p_lo p_hi [threads] (2n <= 64)9 */10#include <stdio.h>11#include <stdlib.h>12#include <string.h>13#include <stdint.h>14#include <pthread.h>1516typedef uint64_t mask;17static int n, k, N;18static mask nb[64];19static int plo, phi, nthreads;20static unsigned long long hist[64][65];21static pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;22static volatile long next_item = 0;2324static void build(void) {25 N = 2 * n;26 memset(nb, 0, sizeof nb);27 for (int i = 0; i < n; i++) {28 int u = i, v = n + i;29 nb[u] |= (mask)1 << ((i + n - 1) % n); nb[u] |= (mask)1 << ((i + 1) % n); nb[u] |= (mask)1 << v;30 nb[v] |= (mask)1 << (n + (i + n - k) % n); nb[v] |= (mask)1 << (n + (i + k) % n); nb[v] |= (mask)1 << u;31 }32 for (int w = 0; w < N; w++) if (__builtin_popcountll(nb[w]) != 3) { fprintf(stderr, "degree != 3\n"); exit(3); }33}3435static void *worker(void *a) {36 (void)a;37 unsigned long long local[64][65]; memset(local, 0, sizeof local);38 int idx[64];39 for (;;) {40 pthread_mutex_lock(&mu); long item = next_item++; pthread_mutex_unlock(&mu);41 int p = plo + (int)(item / N), first = (int)(item % N);42 if (p > phi) break;43 if (p == 0) { if (first == 0) local[p][0]++; continue; }44 if (N - first < p) continue;45 for (int i = 0; i < p; i++) idx[i] = first + i;46 for (;;) {47 mask X = 0, NX = 0;48 for (int i = 0; i < p; i++) { X |= (mask)1 << idx[i]; NX |= nb[idx[i]]; }49 local[p][__builtin_popcountll(NX & ~X)]++;50 int i = p - 1;51 while (i >= 1 && idx[i] == N - p + i) i--;52 if (i < 1) break;53 idx[i]++;54 for (int j = i + 1; j < p; j++) idx[j] = idx[j - 1] + 1;55 }56 }57 pthread_mutex_lock(&mu);58 for (int p = 0; p < 64; p++) for (int b = 0; b <= 64; b++) hist[p][b] += local[p][b];59 pthread_mutex_unlock(&mu);60 return NULL;61}6263int main(int argc, char **argv) {64 if (argc < 5) { fprintf(stderr, "usage: beta_brute n k p_lo p_hi [threads]\n"); return 2; }65 n = atoi(argv[1]); k = atoi(argv[2]); plo = atoi(argv[3]); phi = atoi(argv[4]);66 nthreads = argc > 5 ? atoi(argv[5]) : 1;67 if (2 * n > 64 || n < 2 * k + 1 || phi >= 64) { fprintf(stderr, "bad arguments\n"); return 2; }68 build();69 pthread_t th[64];70 for (int i = 0; i < nthreads; i++) pthread_create(&th[i], NULL, worker, NULL);71 for (int i = 0; i < nthreads; i++) pthread_join(th[i], NULL);72 for (int p = plo; p <= phi; p++) {73 unsigned long long total = 0; int beta = -1;74 for (int b = 0; b <= 64; b++) { total += hist[p][b]; if (hist[p][b] && beta < 0) beta = b; }75 printf("n=%d k=%d p=%d subsets=%llu beta=%d hist=", n, k, p, total, beta);76 for (int b = 0; b <= 64; b++) if (hist[p][b]) printf("%d:%llu ", b, hist[p][b]);77 printf("\n");78 }79 return 0;80}81