From GAP-Forum-Sender@Math.RWTH-Aachen.DE Mon Mar 25 17:22 EST 1996
Return-Path: <GAP-Forum-Sender@Math.RWTH-Aachen.DE>
Received: from sma.usna.navy.MIL (math3) by math65.usna.navy.MIL (5.x/SMI-SVR4)
	id AA01782; Mon, 25 Mar 1996 17:22:05 -0500
Received: from hurin.math.rwth-aachen.de by sma.usna.navy.MIL (4.1/SMI-4.1)
	id AA29511; Mon, 25 Mar 96 17:17:57 EST
Received: from samson.math.rwth-aachen.de by hurin.math.rwth-aachen.de with smtp
	(Smail3.1.28.1 #30) id m0u0t2J-0009deC.960325.231517; Sun, 24 Mar 96 17:52 MET
Received: by samson.math.rwth-aachen.de (Smail3.1.28.1 #11)
	id m0u0t2H-000I7zC; Sun, 24 Mar 96 18:52 MET DST
Errors-To: GAP-Forum-Errors@Math.RWTH-Aachen.DE
Errors-To: GAP-Forum-Errors@Math.RWTH-Aachen.DE
Message-Id:     <9603241646.AA16239@csia.csi.uottawa.ca>
Sender: GAP-Forum-Sender@Math.RWTH-Aachen.DE
Errors-To: GAP-Forum-Errors@Math.RWTH-Aachen.DE
Reply-To: GAP Forum <GAP-Forum-Reply@Math.RWTH-Aachen.DE>
X-Miles:        GAP Forum article 872 accepted at 24 Mar 96 18:50 +0100
Date:           Sun, 24 Mar 96 11:46:54 -0500 (EST)
From: Istvan <u640486@csi.uottawa.ca>
To: Multiple recipients of list <GAP-Forum@Math.RWTH-Aachen.DE>
Subject:        Shorter Words With AbStab
Content-Type: text
Content-Length: 4713
X-Lines: 194
Status: RO

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