// posetlib.js v2 - exact poset toolkit: complete labeled generator + fast exact pair probabilities
function transitiveClosure(n, relIn){var r=relIn.slice();for(var k=0;k<n;k++)for(var u=0;u<n;u++)if((r[u]>>k)&1)r[u]|=r[k];return r;}
function predecessorsMask(n, rel){var p=new Array(n).fill(0);for(var u=0;u<n;u++){var m=rel[u];while(m){var v=31-Math.clz32(m&-m);p[v]|=(1<<u);m&=m-1;}}return p;}
function relFromEdges(n, edges){var r=new Array(n).fill(0);for(var i=0;i<edges.length;i++){r[edges[i][0]]|=(1<<edges[i][1]);}return transitiveClosure(n,r);}
function isChainPoset(n, rel){for(var i=0;i<n;i++)for(var j=i+1;j<n;j++)if(!(((rel[i]>>j)|(rel[j]>>i))&1))return false;return true;}
function linExtCount(n, rel){var pred=predecessorsMask(n,rel);var size=1<<n;var dp=new Float64Array(size);dp[0]=1;for(var mask=0;mask<size;mask++){var d=dp[mask];if(!d)continue;var a=(~mask)&(size-1);while(a){var x=31-Math.clz32(a&-a);if((pred[x]&~mask)===0)dp[mask|(1<<x)]+=d;a&=a-1;}}return dp[size-1];}
// e(I): extensions whose first |I| elements form ideal I; eC(J): orderings of induced subposet J
function tablesE(n, rel){var size=1<<n;var pred=predecessorsMask(n,rel);var e=new Float64Array(size);e[0]=1;
 for(var m=1;m<size;m++){var s=0,a=m;while(a){var x=31-Math.clz32(a&-a);a&=a-1;if((pred[x]&~m)===0)s+=e[m^(1<<x)];}e[m]=s;}
 var eC=new Float64Array(size);eC[0]=1;
 for(var m2=1;m2<size;m2++){var s2=0,b=m2;while(b){var y=31-Math.clz32(b&-b);b&=b-1;if((rel[y]&m2)===0)s2+=eC[m2^(1<<y)];}eC[m2]=s2;}
 return{e:e,eC:eC};}
// nums[x*n+y] = exact number of linear extensions with x before y (integer-valued float64)
function pairNums(n, rel, T){var size=1<<n;var full=size-1;if(!T)T=tablesE(n,rel);var nums=new Float64Array(n*n);var PR=predecessorsMask(n,rel);
 for(var I=0;I<size;I++){var comp=full&~I;if(!comp)continue;
  var a=I;while(a){var x=31-Math.clz32(a&-a);a&=a-1;if(((rel[x]&I)!==0)||((PR[x]&comp)!==0))continue;var w=T.e[I^(1<<x)]*T.eC[comp];if(!w)continue;var b2=comp;var base=x*n;
   while(b2){var y=31-Math.clz32(b2&-b2);b2&=b2-1;nums[base+y]+=w;}}}
 var E=T.e[size-1];return{nums:nums,E:E};}
function gcd(a,b){while(b){var t=a%b;a=b;b=t;}return a;}
function deltaFromNums(n, nums, E){var bn=-1,bd=1,bp=[-1,-1],cnt=0;
 for(var x=0;x<n;x++)for(var y=x+1;y<n;y++){cnt++;var pnum=nums[x*n+y],qnum=nums[y*n+x];var m=Math.min(pnum,qnum);
  if(m*bd>bn*E){bn=m;bd=E;bp=[x,y];}}return{num:bn,den:bd,pair:bp,nPairs:cnt,E:E};}
function deltaFast(n, rel){var t=tablesE(n,rel);var pn=pairNums(n,rel,t);return deltaFromNums(n,pn.nums,pn.E);}
// brute-force reference: per-pair forced DP
function deltaBrute(n, rel){var E=linExtCount(n,rel);var bn=-1,bd=1,bp=[-1,-1];
 for(var x=0;x<n;x++)for(var y=x+1;y<n;y++){var Eyx;
  if((rel[y]>>x)&1)Eyx=null;else if((rel[x]>>y)&1)Eyx=0;else{var r=rel.slice();r[y]|=(1<<x);Eyx=linExtCount(n,transitiveClosure(n,r));}
  var pnum=E-Eyx;var m=Math.min(pnum,Eyx);if(m*bd>bn*E){bn=m;bd=E;bp=[x,y];}}return{num:bn,den:bd,pair:bp};}
// complete labeled poset generator: assign each old element as below/incomparable/above the new one
function genAllLabeledPosets(n, visit){
 if(n===1){visit([0]);return;}
 function rec(k, rel, D, U, una){
  if(una===0){var chk=D,dok=true;while(chk&&dok){var cx=31-Math.clz32(chk&-chk);chk&=chk-1;var cu=U;while(cu){var cy=31-Math.clz32(cu&-cu);cu&=cu-1;if(!((rel[cx]>>cy)&1)){dok=false;break;}}}if(!dok)return;var r2=rel.slice();var d=D;while(d){var xx=31-Math.clz32(d&-d);r2[xx]|=(1<<k);d&=d-1;}var u=U;while(u){var yy=31-Math.clz32(u&-u);r2[k]|=(1<<yy);u&=u-1;}k++;if(k===n){visit(r2);return;}rec(k,r2,0,0,(1<<k)-1);return;}
  var pr=predecessorsMask(k,rel);var x=31-Math.clz32(una&-una),una2=una^(1<<x),xb=1<<x;
  if(((pr[x]&U)===0)&&((pr[x]&~(D|una2))===0))rec(k,rel,D|xb,U,una2);
  if(((rel[x]&D)===0)&&((rel[x]&~(U|una2))===0))rec(k,rel,D,U|xb,una2);
  if(((rel[x]&D)===0)&&((pr[x]&U)===0))rec(k,rel,D,U,una2);
 }
 rec(1,new Array(n).fill(0),0,0,1);
}
function idealsOf(n, rel){var out=[];var pred=predecessorsMask(n,rel);function rec(mask,start){out.push(mask);for(var x=start;x<n;x++){if(mask&(1<<x))continue;if(pred[x]&~mask)continue;rec(mask|(1<<x),x+1);}}rec(0,0);return out;}
function permToRel(pi){var n=pi.length,r=new Array(n).fill(0);for(var i=0;i<n;i++)for(var j=0;j<n;j++)if(i<j&&pi[i]<pi[j])r[i]|=(1<<j);return r;}
function forEachPerm(n, visit){var a=[];for(var i=0;i<n;i++)a.push(i);function rec(k){if(k===n){visit(a.slice());return;}for(var i=k;i<n;i++){var t=a[k];a[k]=a[i];a[i]=t;rec(k+1);t=a[k];a[k]=a[i];a[i]=t;}}rec(0);}
function is22Free(n, rel){function inc(u,v){return !(((rel[u]>>v)|(rel[v]>>u))&1);}for(var a=0;a<n;a++)for(var b=0;b<n;b++)if((rel[a]>>b)&1)for(var c=0;c<n;c++)for(var d=0;d<n;d++)if((rel[c]>>d)&1){if(a===c&&b===d)continue;if(inc(a,c)&&inc(a,d)&&inc(b,c)&&inc(b,d))return false;}return true;}
function coverEdges(n, rel){var e=[];for(var u=0;u<n;u++){var m=rel[u];while(m){var v=31-Math.clz32(m&-m);m&=m-1;var between=false;for(var w=0;w<n;w++){if(w!==u&&w!==v&&((rel[u]>>w)&1)&&((rel[w]>>v)&1)){between=true;break;}}if(!between)e.push([u,v]);}}return e;}
function dualOf(n, rel){var r=new Array(n).fill(0);for(var u=0;u<n;u++){var m=rel[u];while(m){var v=31-Math.clz32(m&-m);r[v]|=(1<<u);m&=m-1;}}return r;}
module.exports={transitiveClosure:transitiveClosure,predecessorsMask:predecessorsMask,relFromEdges:relFromEdges,isChainPoset:isChainPoset,linExtCount:linExtCount,tablesE:tablesE,pairNums:pairNums,deltaFast:deltaFast,deltaBrute:deltaBrute,genAllLabeledPosets:genAllLabeledPosets,idealsOf:idealsOf,permToRel:permToRel,forEachPerm:forEachPerm,is22Free:is22Free,coverEdges:coverEdges,dualOf:dualOf};

if(require.main===module){
 function fmt(d){return d.num+"/"+d.den+" @"+JSON.stringify(d.pair);}
 var ac=P0();function P0(){return require("./posetlib.js");}
 var P=P0();
 var t0=Date.now();
 var d1=P.deltaFast(3,P.relFromEdges(3,[]));
 console.log("T1 antichain3:",fmt(d1),(d1.num*2===d1.den)?"OK":"FAIL");
 var d2=P.deltaFast(3,P.relFromEdges(3,[[0,1],[0,2]]));
 console.log("T2 V-poset:",fmt(d2),(d2.num*2===d2.den)?"OK":"FAIL");
 var np=P.relFromEdges(4,[[0,1],[2,1],[2,3]]);var d3=P.deltaFast(4,np),d3b=P.deltaBrute(4,np);
 console.log("T3 N-poset fast:",fmt(d3),"brute:",fmt(d3b),(d3.num===d3b.num&&d3.den===d3b.den)?"AGREE":"MISMATCH");
 var expect=[0,0,3,19,219,4231,130023];var okAll=true;
 for(var nn=2;nn<=6;nn++){var c=0;P.genAllLabeledPosets(nn,function(){c++;});var ok=(c===expect[nn]);okAll=okAll&&ok;console.log("T4 count n="+nn+":",c,"expect",expect[nn],ok?"OK":"FAIL");}
 // cross-validate fast vs brute on every poset on 5 elements
 var mism=0,tot=0,min=null,minimizers=[];
 P.genAllLabeledPosets(5,function(rel){tot++;if(P.isChainPoset(5,rel))return;
  var df=P.deltaFast(5,rel),db=P.deltaBrute(5,rel);
  if(df.num!==db.num||df.den!==db.den)mism++;
  if(min===null||df.num*min.den<min.num*df.den){min=df;minimizers=[rel];}else if(df.num*min.den===min.num*df.den)minimizers.push(rel);
 });
 console.log("T5 n=5 fast-vs-brute mismatches:",mism,"of",tot,mism===0?"OK":"FAIL");
 console.log("T5 min delta over all non-chain posets n=5:",fmt(min),"labeled minimizers:",minimizers.length);
 console.log("T5 example minimizer covers:",JSON.stringify(P.coverEdges(5,minimizers[0])));
 var pm=null,pmCov=null;
 P.forEachPerm(7,function(pi){var r=P.permToRel(pi);if(P.isChainPoset(7,r))return;var d=P.deltaFast(7,r);if(pm===null||d.num*pm.den<pm.num*d.den){pm=d;pmCov=P.coverEdges(7,r);}});
 console.log("T6 min delta over dim-2 posets n=7:",fmt(pm));
 console.log("elapsed ms:",Date.now()-t0,"toolkit OK" );
}