Hi,

Recently I was playing around with the ordering of the points in the
stabilizer. I "invented" a heuristic that seems to dramatically improve the
word-length for the Rubik's Cube. I tried it on different permutation
groups as well. In general it does not improve for randomly generated
groups, but it does not seem to increase the word length either. For
groups "similar" to the Cube the improvement holds.

I ran a test of sample size 500 on the Cube. Using FactorPermGroupElement
without shrinking I obtained 86.528 % shorter paths. The lowest
improvement was 43% while the highest 97%. Using Shrink the word length
usually gets below 100.

The paths were all tested algebraically and "visually". I made up a simple
description language that generates displays for permutation groups.

The problem I am having is, that I cannot explain myself why it works so
well. I include here the few functions that make up the heuristic, and how
to use it. Anyone interested, please feel free to use it. I would truely
appreciate any comments and maybe even an explanation. (I am not a
mathematician, just a "poor" undergrad in Computer Science).

How to use it??

Very easy. Set a field "heuristic" to true for the group you are passing
to FactorPermGroupElement or Shrink.

like:
cube.heuristic:=true;

FactorPermGroupElement(cube,Random(cube));

Changes to AbStab.

Almost nothing:

Add the four lines to MakeStab or MakeShortStab here:

Append(base, Difference( PermGroupOps.MovedPoints( G ), base ) );

##########################################################
# Add The next 4 lines here in MakeSatb or MakeShortSatb #
##########################################################
if IsBound(G.heuristic) and G.heuristic
then
  base := Reversed(SortByGeneratorsOnOrbits(G,base));
fi;

l := 1;
while l <= Length( base ) and
            ForAll( gens, gen -> base[l] ^ gen = base[l] )  do
    l := l + 1;
od;

And add the next four lines in MakeAbStabChain:

G.stabilizerSubgroup := H;

#############################################
# Add these next four lines here            #
#############################################
if IsBound(G.heuristic) and G.heuristic
then
  H.heuristic := true;
fi;

MakeAbStabChain( H, l );

The functions. I call the file "strip.g". Make sure AbStab.g reads them.

Here are all:

sortfunc := function(L1,L2)
  return Length(L1) < Length(L2);
end; # sortfunc

LargestPoint := function(G)
local Result,L;

Result := 0;
L := PermGroupOps.MovedPoints(G);

if Length(L) > 0
then
  Result := Maximum(L);
fi;

return Result;
end; # LargestPoint

TrivialBase := function(G)
local orbitGroup,orbit,coupledElements,head;

  if not IsBound(G.trivialBase)
  then
     G.trivialBase := [];
     if not IsBound(G.orbits)
     then
        G.orbits := Orbits(G,[1..LargestPoint(G)]);
        Sort(G.orbits,sortfunc);
     fi;
     for orbit in [1 .. Length(G.orbits)]
     do
       orbitGroup := Operation(G,G.orbits[orbit]);
       coupledElements := Blocks(orbitGroup,[1..Length(G.orbits[orbit])]);
       for head in [1..Length(coupledElements)]
       do
         Add(G.trivialBase,G.orbits[orbit][coupledElements[head][1]]);
       od;
     od;
  fi;
end; # TrivialBase

StripBase := function(G,L)
local Result,element;

Result := [];
TrivialBase(G);
for element in [1 .. Length(L)]
do
if L[element] in G.trivialBase
then
Add(Result,L[element]);
fi;
od;

return Result;
end; # StripBase

SortByGeneratorsOnOrbits := function(G,L)
local i,j,genpoints,list,list2,Result1,Result;

genpoints := [];
Result := [];
Result1 := [];

for i in [1..Length(G.generators)]
do
  list := Cycles(G.generators[i],
                 [
                  SmallestMovedPointPerm(G.generators[i])
                  ..
                  LargestMovedPointPerm(G.generators[i])
                 ]
                );
  list2 := [];
  for j in [1..Length(list)]
  do
    if Length(list[j]) > 1
    then
      Add(list2,list[j]);
    fi;
  od;
  list2 := Flat(list2);
  for j in [1..Length(list2)]
  do
    if not list2[j] in Result1
    then
      Add(Result1,list2[j]);
    fi;
  od;
od;

Result1 := StripBase(G,Result1);

for i in [1..Length(Result1)]
do
  if Result1[i] in L and not Result1[i] in Result
  then
    Add(Result,Result1[i]);
  fi;
od;

return Result;
end;

Thanks,

--

- Istvan

Istvan T. Hernadvolgyi | http://www.csi.uottawa.ca/~u640486
u640486@csi.uottawa.ca |   (Canada) -( 613 ) - 749 - 5191