Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- denseform(n, coeff)={
- local(f); f = vector(n);
- for(i=1, matsize(coeff)[1], f[coeff[i,1]]+=coeff[i,2]);
- f;
- }
- \\ inequality t_{ij} > t_{ik}, that is, (k-j)v_i + (i-k) v_j + (j-i) v_k > 0
- \\ (for i < j < k)
- collideright(n, i,j,k)=denseform(n, [i, k-j; j, i-k; k, j-i]);
- collideleft(n, i,j,k) =-collideright(n, i,j,k);
- collide(n, i,j) = denseform(n, [i,1;j,-1]);
- notcollide(n, i,j) = -collide(n, i, j);
- ineq(s)={
- local(l, d, depth, match, R);
- l=Vec(s); depth=vector(#l); d=0;
- for(i=1, #l, depth[i]=d; d+=(l[i]=="(")-(l[i]==")"));
- match=vector(#l);
- for(i=1, #l, if(l[i]=="(", for(j=i+1, #l,
- if(depth[j]==depth[i]+1 && l[j]==")", match[i]=j; match[j]=i; next (2)))));
- R=[];
- for(i1=1,#l,
- if (l[i1] == "(", j1=match[i1];
- \\ (): v_i > v_j
- R = concat(R, [collide(#l, i1, j1)]);
- \\ (())
- for (i2=i1+1, j1-1, if (l[i2] == "(", j2=match[i2];
- R = concat (R,
- [collideright (#l, i1, i2, j2), collideleft (#l, i2, j2, j1)])));
- \\ ()()
- for (i2=j1+1, #l, if (l[i2] == "(", j2=match[i2];
- R = concat (R,
- [collideleft (#l, i1, j1, i2), collideright (#l, j1, i2, j2)])))
- , if (l[i1] != ")", \\ escaped bullet
- \\ !! and !()
- for (i2=i1+1, #l, if (l[i2]!=")",
- R = concat (R, [notcollide (#l, i1, i2)])));
- \\ ()! (!! already done)
- for (i2=1, i1-1, if (l[i2]==")",
- R = concat (R, [notcollide (#l, i2, i1)])));
- ))
- );
- R;
- }
- polytope(s)={
- local(R); R=ineq(s);
- concat([vector(#R, i, vector(#s+1,j,if(j<=#s, R[i][j]))),
- vector(#s,i, vector(#s+1,j, j==i)),
- vector(#s,i, vector(#s+1,j, (j>#s)-(j==i)))]);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement