Alexander—
This was indeed very helpful. Here is my version of the code:
NewDCCounter := function(g, u, v)
return rec(
g := g,
u := u,
v := v,
max_idx := 0,
dc_number := [],
t := RightTransversal(g, u),
counts := []);
end;;
AddDCCounter := function(dcc, r)
local dcn, i, o;
p := PositionCanonical(dcc.t, r); # Number of the right coset for
the element.
if IsBound(dcc.dc_number[p]) then
dcn := dcc.dc_number[p];
dcc.counts[dcn] := dcc.counts[dcn] + 1;
else
dcc.max_idx := dcc.max_idx + 1;
dcc.counts[dcc.max_idx] := 1;
dcc.dc_number[p] := dcc.max_idx;
# Mark all right cosets within the same double coset, via
# orbit of right coset (dcc.u, t[p]) under dcc.v by right
multiplication.
o := Orbit(dcc.v, CanonicalRightCosetElement(dcc.u, dcc.t[p]),
#o := Orbit(dcc.v, dcc.t[p],
function(pnt, s)
return CanonicalRightCosetElement(dcc.u, pnt*s);
end);
for i in o do
dcc.dc_number[PositionCanonical(dcc.t, i)] := dcc.max_idx;
od;
fi;
end;;
and it in action:
gap> mdcc := NewDCCounter(SymmetricGroup(4),
Subgroup(g,[(1,2,3),(1,2)]), Subgroup(g,[(3,4)]));
rec( counts := [ ], dc_number := [ ], g := Sym( [ 1 .. 4 ] ), max_idx := 0,
t := RightTransversal(Sym( [ 1 .. 4 ] ),Group([ (1,2,3), (1,2) ])),
u := Group([ (1,2,3), (1,2) ]),
v := Group([ (3,4) ]) )
gap> AddDCCounter(mdcc, (1,2)); mdcc;
rec( counts := [ 1 ], dc_number := [ 1,,, 1 ], g := Sym( [ 1 .. 4 ] ),
max_idx := 1,
t := RightTransversal(Sym( [ 1 .. 4 ] ),Group([ (1,2,3), (1,2) ])),
u := Group([ (1,2,3), (1,2) ]),
v := Group([ (3,4) ]) )
gap> AddDCCounter(mdcc, (1,2,3)); mdcc;
rec( counts := [ 2 ], dc_number := [ 1,,, 1 ], g := Sym( [ 1 .. 4 ] ),
max_idx := 1,
t := RightTransversal(Sym( [ 1 .. 4 ] ),Group([ (1,2,3), (1,2) ])),
u := Group([ (1,2,3), (1,2) ]),
v := Group([ (3,4) ]) )
gap> AddDCCounter(mdcc, (1,2,4)); mdcc;
rec( counts := [ 2, 1 ], dc_number := [ 1, 2,, 1 ], g := Sym( [ 1 .. 4
] ), max_idx := 2,
t := RightTransversal(Sym( [ 1 .. 4 ] ),Group([ (1,2,3), (1,2) ])),
u := Group([ (1,2,3), (1,2) ]),
v := Group([ (3,4) ]) )
gap>
gap> AddDCCounter(mdcc, (2,4)); mdcc;
rec( counts := [ 2, 1, 1 ], dc_number := [ 1, 2, 3, 1 ], g := Sym( [ 1
.. 4 ] ), max_idx := 3,
t := RightTransversal(Sym( [ 1 .. 4 ] ),Group([ (1,2,3), (1,2) ])),
u := Group([ (1,2,3), (1,2) ]),
v := Group([ (3,4) ]) )
gap>
gap> AddDCCounter(mdcc, (1,4)); mdcc;
rec( counts := [ 2, 2, 1 ], dc_number := [ 1, 2, 3, 1 ], g := Sym( [ 1
.. 4 ] ), max_idx := 3,
t := RightTransversal(Sym( [ 1 .. 4 ] ),Group([ (1,2,3), (1,2) ])),
u := Group([ (1,2,3), (1,2) ]),
v := Group([ (3,4) ]) )
gap>
gap> AddDCCounter(mdcc, (1,4)); mdcc;
rec( counts := [ 2, 3, 1 ], dc_number := [ 1, 2, 3, 1 ], g := Sym( [ 1
.. 4 ] ), max_idx := 3,
t := RightTransversal(Sym( [ 1 .. 4 ] ),Group([ (1,2,3), (1,2) ])),
u := Group([ (1,2,3), (1,2) ]),
v := Group([ (3,4) ]) )
gap>
Please let me know if there is anything I can do with respect to Broader
Impacts. It looks like I’ll be giving a talk in the 2016 AMS conference in
Seattle, so perhaps we can meet then.
Erick
On Tue, Mar 10, 2015 at 7:57 AM, Alexander Hulpke <hul...@fastmail.fm>
wrote:
> 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/
>
>
--
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
