Dear Erick, >> There are really two answers to your question. >> The first is the actual question — how to change the stored values of >> dictionaries. Here my choice (as the person who implemented much of the code >> for dictionaries) would be to not to attempt to change the values at all, >> but use as values the entries in a (changeable) value list. While this >> requires one indirection it is safe and requires no modification of data >> structures that might not have been set up for this, or might change in >> future releases (in fact is almost guaranteed to do so as there are still >> some issues in the code). >> >> > I tried doing this, but once I stored the list in the dictionary I found I > could no longer change the list. > > gap> l := [3]; > [ 3 ] > gap> d := NewDictionary(false, true, [1,2,3]); > <object> > gap> IsMutable(l); > true > gap> AddDictionary(d, 2, l); > gap> IsMutable(l); > false > gap> > > Am I confused?
No. The current code for dictionaries potentially makes (without warning or other niceties) the values of a dictionary immutable. Thus my suggestion for storing the index positions in another list: gap> d := NewDictionary(false, true, [1,2,3]); <object> gap> values:=[]; [ ] gap> cnt:=0; 0 gap> cnt:=cnt+1;values[cnt]:=[];AddDictionary(d,2,cnt); 1 [ ] gap> cnt:=cnt+1;values[cnt]:=[];AddDictionary(d,5,cnt); 2 [ ] gap> values[LookupDictionary(d,5)]; [ ] gap> AddSet(values[LookupDictionary(d,5)],'A'); gap> AddSet(values[LookupDictionary(d,5)],'Z'); gap> values[LookupDictionary(d,5)]; "AZ" >> At the moment GAP has no specific hash key code for double cosets, so the >> best dictionaries can do is to compare using the `<‘ order. For double >> cosets, this comparison is done by determining the (minimal) representatives >> for all the contained right cosets, and comparing the smallest of the >> minimal coset representatives. While this ordering is equivalent to the >> ordering as sets of elements, if means that in fact you store >> representatives for all right cosets. Given that this is the case, I would >> try the following approach (assuming the subgroups are A and B): >> > > Here again I think I must be confused: > > gap> g:=SymmetricGroup(4);; > gap> u:=Subgroup(g,[(1,2,3),(1,2)]);; > gap> v:=Subgroup(g,[(3,4)]);; > gap> cos:=DoubleCosets(g, u, v); > [ DoubleCoset(Group( [ (1,2,3), (1,2) ] ),(),Group( [ (3,4) ] )), > DoubleCoset(Group( [ (1,2,3), (1,2) ] ),(1,4),Group( [ (3,4) ] )), > DoubleCoset(Group( [ (1,2,3), (1,2) ] ),(1,4,2),Group( [ (3,4) ] )) ] > gap> cos[1] < cos[2]; Ah -- then there actually isn't yet such a comparison of double cosets (as described) , which means the dictionary code can rely only on comparing for equality (and linear search). Then using only right cosets is definitively faster. > > Regarding publications, etc, we will be submitting a paper in early April to > the FOCS CS conference, and will put it on the arXiv. Thank you! Alexander > I’d love to help out in any way I can. > > Erick > > > > > Calculate t:=RightTransversal(G,A) > This is an object that behaves like a list, but often needs less storage. > > Create a second list DCNumber that for each right coset of A stores the > number (in some arbitrary indexing) of the double coset AxB that contains A. > > If you find an element r, let > > p:=PositionCanonical(t,r); # number of the right coset for the element > if IsBound(DCNumber[p]) then > result:=DCNumber[p]; > else > newnum:=New index number for double coset; > result:=newnum; > DCNumber[p]:=newnum; > o:=Orbit(B,t[p],function(rep,g) return > CanonicalRightCosetElement(A,rep*g);end); > for i in o do > DCNumber[PositionCanonical(t,i)]:=newnum; # mark all right cosets within > the same double coset. > od; > fi; > > and then process result — the number of the double coset — as if it came as > dictionary value. This is less slick code than dictinaries, but I’d suspect > this will work notably faster. > > Best, > > Alexander Hulpke > >> Frederick "Erick" Matsen, Assistant Member >> Fred Hutchinson Cancer Research Center > > Is there a chance you have a citable article or presentation that connects > permutation group calculations with (the ultimate ``usefulness’’ argument for > higher administration) attempts on dealing with cancer? This could come very > helpful when questions of ``broader impace’’ etc. come up. Thanks! > > > -- Alexander Hulpke. Department of Mathematics, Colorado State University, > Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA > email: hul...@math.colostate.edu, Phone: ++1-970-4914288 > http://www.math.colostate.edu/~hulpke > > > > -- > Frederick "Erick" Matsen, Assistant Member > Fred Hutchinson Cancer Research Center > http://matsen.fredhutch.org/ _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum
