OldHelp:=proc(): print(` Sphere(pi,k), flip(pi,i) `): print(`Ball(pi,k) , BFPF(pi), Pad(T) `): end: Help:=proc(): print(`Pad(T), IsSV(L), flipT(T,i) `): print(`BFTF(T) , GatesTypes() `): end: #[[0,0],0,[1,1],0,[-1,0]] #c(o=-1) [t, BLANK, [..... t-1], BLANK, [.... t+1] #[[0,0],0,[-1,1],0,[1,-1]] flip:=proc(pi,i) local j: [seq(pi[i+1-j],j=1..i),op(i+1..nops(pi),pi)]: end: #Ball(pi,k): all the permutations of distance #<=k from pi Ball:=proc(pi,k) local i,s: option remember: {seq(seq(s[1], s in Sphere(pi,i)),i=0..k)}: end: #Spehere(pi,k): all the permutations, followed #by the list of flips, distance k from pi #For example, Sphere([2,1],1); should #output {[[1,2],[2]]}; Sphere:=proc(pi,k) local S,i,n,baxter,s,Andrew,Nei,ne: option remember: n:=nops(pi): if k=0 then RETURN({[pi,[]]}): fi: if k=1 then RETURN({seq([flip(pi,i),[i]],i=2..n )}): fi: S:=Sphere(pi,k-1): baxter:={}: Andrew:=Ball(pi,k-1): for s in S do Nei:=Sphere(s[1],1): for ne in Nei do if not member(ne[1],Andrew) then baxter:=baxter union {[ne[1],[op(s[2]),op(ne[2])]]}: Andrew:=Andrew union {ne[1]}: fi: od: od: baxter: end: #BFPF(pi): inputs a permutation pi and #outputs ONE list of flips making it #[1, ..., nops(pi)] BFPF:=proc(pi) local n,i,S,s,susan: n:=nops(pi): susan:=[seq(i, i=1..n)]: for i from 0 to 300*n do S:=Sphere(pi,i): for s in S do if s[1]=susan then RETURN(s[2]): fi: od: od: FAIL: end: ###New stuff for March 31, 2011 #inputs a type (a list of pairs) and outputs #the same list with 0's between any consecutive #entries. For example Pad([[1,1],[3,-1],[2,1]]); #should be [[1,1],0,[3,-1],0,[2,1]]; Pad:=proc(T) local i: [seq(op([T[i],0]) ,i=1..nops(T)-1),T[nops(T)]]: end: #IsSV(L): inputs a padded type and checks #whether it is "sorted" #(i): All the 0's must be at the beginning or the end #(ii) the first elements of the pairs must be either #increasing (and then the second elemets must all be #0's or 1's or #decreasing (and then the second elements must all be #0's or -1's. For example #IsSV([0,0,[1,1],[2,1],0,0]); should be true #IsSV([0,[1,1],[2,-1],0]); should be false IsSV:=proc(L) local i,j,k,jake,simao: for i from 1 to nops(L) while L[i]=0 do od: for j from nops(L) to 1 by -1 while L[j]=0 do od: i,j: for k from i+1 to j-1 do if L[k]=0 then RETURN(false): fi: od: jake:=[seq(L[k][1],k=i..j)]: if nops(jake)=1 then RETURN(true): fi: if nops({seq(sign(jake[k+1]-jake[k]),k=1..nops(jake)-1)})>1 then RETURN(false): fi: simao:=[seq(L[k][2],k=i..j)]: if jake[2]-jake[1]>0 then if convert(simao,set) subset {0,1} then RETURN(true): fi: elif jake[2]-jake[1]<0 then if convert(simao,set) subset {0,-1} then RETURN(true): fi: fi: false: end: #BFTF(T): inputs a type T and #outputs ONE list of flips making it #a sorted version BFTF:=proc(T) local i,S,s: option remember: for i from 0 to nops(T)*300 do S:=SphereT(T,i): for s in S do if IsSV(s[1]) then RETURN(s[2]): fi: od: od: FAIL: end: #flipT([0,[1,-1],0,[2,1],0,[3,-1]],4); #should be [[2,-1],0,[1,1],0,[3,-1]] #flips a padded type at the i-th location flipT:=proc(T,i) local j,L: L:=[]: for j from i by -1 to 1 do if T[j]=0 then L:=[op(L),0]: else L:=[op(L), [T[j][1],-T[j][2]] ]: fi: od: [ op(L) , op(i+1..nops(T),T)]: end: #SphereT(T,k): all the padded types, followed #by the list of flips, distance k from T #For example, Sphere([[2,1]],1); should #output {[ [[2,-1]],[1]]}; SphereT:=proc(T,k) local S,i,n,baxter,s,Andrew,Nei,ne: option remember: n:=nops(T): if k=0 then RETURN({[T,[]]}): fi: if k=1 then RETURN({seq([flipT(T,i),[i]],i=1..n )}): fi: S:=SphereT(T,k-1): baxter:={}: Andrew:=BallT(T,k-1): for s in S do Nei:=SphereT(s[1],1): for ne in Nei do if not member(ne[1],Andrew) then baxter:=baxter union {[ne[1],[op(s[2]),op(ne[2])]]}: Andrew:=Andrew union {ne[1]}: fi: od: od: baxter: end: #BallT(T,k): all the padded types of distance #<=k from pi BallT:=proc(T,k) local i,s: option remember: {seq(seq(s[1], s in SphereT(T,i)),i=0..k)}: end: #GatesTypes(): The 18 types of Bill Gates GatesTypes:=proc(): [ #a (o=1) [[0,0],0,[1,0]], #a (o=-1) [[0,0],0,[-1,0]], #b (o=1) [[0,0],0,[1,1]], #b (o=-1) [[0,0],0,[-1,-1]], #c (o=1) [[0,0],0,[1,-1],0,[-1,1]], #c (o=-1) [ [0,0],0,[-1,1],0,[1,-1]], #d (o=1) [[0,-1],0,[1,0]], #d (o=-1) [[0,1],0,[-1,0]], #e (o=1) [[0,-1],0,[1,1]], #e ( o=-1) [[0,1],0,[-1,-1]], #f (o=1) [[0,1],0,[1,0],0,[-1,1]], #f (o=-1) [[0,-1],0,[-1,0],0,[1,-1]], # g (o=1) [[0,1],0,[-1,1],0,[1,0]], #g (o=-1) [[0,-1],0,[1,-1],0,[-1,0]], #h (o=1) [[0,1],0,[1,1]], #h (o=-1) [[0,-1],0,[-1,-1]], #k (o=1) [[0,1],0,[1,-1]], #k (o=-1) [[0,-1],0,[-1,1]] ]: end: