From u640486@csi.UOttawa.CA Tue Feb  6 22:21 EST 1996
Return-Path: <u640486@csi.UOttawa.CA>
Received: from sma.usna.navy.MIL (math3) by math65.usna.navy.MIL (5.x/SMI-SVR4)
	id AA02394; Tue, 6 Feb 1996 22:20:59 -0500
Received: from mail.csi.UOttawa.CA by sma.usna.navy.MIL (4.1/SMI-4.1)
	id AA07282; Tue, 6 Feb 96 22:17:23 EST
Received: from csia.csi.uottawa.ca (u640486@csia.csi.uottawa.ca [137.122.16.2]) by mail.csi.UOttawa.CA (8.6.9/8.6.9) with SMTP id WAA25488 for <wdj@sma.usna.navy.mil>; Tue, 6 Feb 1996 22:17:10 -0500
Received: by csia.csi.uottawa.ca (4.1/8.6.9) id AA20384 for wdj@sma.usna.navy.mil; Tue, 6 Feb 96 22:17:08 EST
From: Istvan <u640486@csi.UOttawa.CA>
Message-Id: <9602070317.AA20384@csia.csi.uottawa.ca>
Subject: cube.g
To: wdj@sma.usna.navy.MIL
Date: Tue, 6 Feb 96 22:17:08 EST
X-Mailer: ELM [version 2.3 PL11]
Content-Type: text
Content-Length: 4196
X-Lines: 138
Status: RO

David,


  Our modem lines were down yesterday, so I don't know if you got my
message.

  I found a "bug" in one of those functions, so here I send the ones I
believe are correct.


#
#
# Miscellaneous functions for cube.g
#
#
# (c) Hernadvolgyi 1996
#
#



#
# Solve for an element "element" of group "g" and return 
# a left-to-right ordered list of generators that would bring
# "element" to the solved group 
#
SolveFromElement := function(g,element,iterationdepth)
  # g is the group
  # element should be a perm-cycle
  # iterationdepth tells how many times the first path is to be shrunk 
  local word,     # word in generators
        counter,  # for number of iterartions
        last,     # the index of the last operation in List(word)
        list,     # converted List(word) to a list of generators
                  # it only means that the path in the generators
                  # is represented in a right-to-left list in reversed order.
                  # We have to convert it into left-to-right correct order
                  # at the end
        Ok;       # This boolean indicates that only iterate until
                  # you can improve on the path, it is checked by the
                  # length of the previous operation-list, if it is not any
                  # shorter don't try to shrink it again
  
  if element in g # is "element" in the group "g" ?
  then
     word := FactorPermGroupElement(g,element); # call AbStab's function
     last := LengthWord(word);                  # record last index

     counter := 1;                              # set counter
     Ok := true;                                # set entry condition

     while counter<iterationdepth and Ok        # start shrinking
       do
         Print("\n Shrinking! from a path of ",last," moves long \n");
         word := Shrink(g,word);
         if LengthWord(word)<last
            then
              last := LengthWord(word);
         else
            Ok := false;   # no improvement leave loop
         fi;
         counter := counter + 1;
       od;
     list := GeneratorListFromWord(word,g);   # convert word to list
      
     return  SolutionOperations(list);        # return solution
                                              # as alist or primary generators
                                              # in left to right order
  else
     Print(element," is not in ",g,"\n");     # trying to solve for an element
                                              # outside the solution space
     return [];                               # return an empty list
  fi;

end; # SolveFromElement


# Display the path "opeartions" that brings "element" to "solved" in
# group g. Of course it is only for the rubik's cube as its display
# is hard-coded
DisplayPath := function(g,solved,element,operations)

    Print("\nStart Solving from:\n");
    DrawCube(List(solved,x->x^(element^-1)),LabelPrint);

    Print("\nSolution:\n");
    OperationOnList(List(solved,x->x^(element^-1)),solved,operations,true,g);
    
    Print("it took ",Length(operations)," operations\n");    
    
end; # DisplayPath


# Display the solution operations which bring "element" to "solved" in 
# group "g" using "iterationdepth" as the upper limit of how many times
# the first path should be shrunk
#
# It needs a display function, so "g" must be "cube"
# solved is [1..48] ie, the points on the cube in the right order
# "element" can be any element of "g" expressed as a perm-cycle
#
# exapmple: SolveAndDisplayFromElement(cube,[1..48],Random(cube.generators),3);
#
# or 
#
# Element := (17,19)(11,8)(6,25)(7,28)(18,21);
#
# SolveAndDisplayFromElement(cube,[1..48],Element,5);
#
SolveAndDisplayFromElement := function(g,solved,element,iterationdepth)
  DisplayPath(g,solved,element,SolveFromElement(g,element,iterationdepth));
end;


GenerateRandomElement := function(generators,length)
  local i,
        elm;
  
  elm := ();
  for i in [1..length]
  do
    elm := elm*Random(generators);
  od;
  
  return elm;
end; # GenerateRandomElement

 

cheers,

-- 

 - Istvan

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