> < ^ From:

< ^ Subject:

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.

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

> < [top]