> < ^ Date: Wed, 03 Apr 1996 09:37:00 +0100 (MET)
> < ^ From: Martin Schoenert <martin.schoenert@math.rwth-aachen.de >
< ^ Subject: Re: Shorter Words With AbStab

Istvan T. Hernadvolgyi wrote in his e-mail message of 1996/03/24

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.


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).

I think I have an idea why your heuristic works.

I think 'SortByGeneratorsOnOrbits' pushes fixpoints of the first
generators to the end of the list. When you then reverse the list,
you move those fixpoints to the front.

The effect is that each step in the stabilizer chain calculation selects
a basepoint which is likely a fixpoint for the first generator(s).
This has the effect of pushing those generators into the stabilizer.

This is good because it means that we have short (as words in the
original generators) generators for the stabilizers. And the shorter
the generators, the shorter the words 'FactorPermGroupElement' returns.

This may also explain why you see less of an effect for randomly
generated groups. Elements of those groups will probably have only very
few fixpoints. So the chance of selecting a basepoint such that more
than one short generator is pushed into the stabilizer is very small.

I leave it to you to devise ways to test this hypothesis.


-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany

> < [top]