« MiniZinc-nyheter | Main | Gruppteoretisk lösning av M12 puzzle i GAP - take 2 »

juni 29, 2008

Gruppteoretisk lösning av M12 puzzle i GAP

I Tre matematiska / logiska pyssel med constraint programming-lösningar: n-puzzle, SETS, M12 (i MiniZinc) presenterades det gruppteoretiska pysslet M12, då med en lösning i MiniZinc (modellen M12.mzn).

När jag läste om M12 tänkte jag att det skulle vara skoj med även en gruppteoretisk lösning eftersom det är ett gruppteoretiskt problem. En sådan lösning har nu gjorts med hjälp av det abstrakta algebraiska systemet GAP. Numera finns GAP även med i distributionen av det öppna matematiska (och mycket trevliga) systemet Sage.

Uppdatering
Efter lite funderande kom jag på en bättre lösning. I stället för att ändra en massa i denna text skrev jag en ny: Gruppteoretisk lösning av M12 puzzle i GAP - take 2, vilken se.


Kort beskrivning av M12
Som tidigare beskrivits går M12-pysslet ut på att man har en sekvens av 12 siffror i en härlig oordning och man ska med hjälp av två operationer återställa sekvensen till 1,2,3,4,5,6,7,8,9,10,11,12. Operationerna är:
Merge: [1, 12, 2, 11,3, 10, 4, 9, 5, 8, 6, 7] blir [1,2,3,4,5,6,7,8,9,10,11,12].
Inverse: Vänder listan om, [1,2,3,4,5,6,7,8,9,10,11,12] blir [12,11,10,9,8,7,6,5,4,3,2,1]. Not, jag kallar operationen (av historiska skäl) för Reverse här nedan.


GAP-program
Här är GAP-programmet (M12_gap.txt). Resultat från ett kommando eller kommentar skrivs efter "#".


Först definierar vi operatorerna, dvs generatorerna i gruppen. Här används PermList som tar en lista och skapar en permutationscykel.

#
# Solving the M12 for a specific sequence
#

#
# Define the operators
#

# Reverse (Inverse)
reverse := PermList([12,11,10,9,8,7,6,5,4,3,2,1]);
# (1,12)(2,11)(3,10)(4,9)(5,8)(6,7)

# Merge
merge := PermList([1,12,2,11,3,10,4,9,5,8,6,7]);
# (2,12,7,4,11,6,10,8,9,5,3)

Skapa gruppen g och gör några tester.


# Create the group
g:=Group([reverse, merge]);
# Group([ (1,12)(2,11)(3,10)(4,9)(5,8)(6,7), (2,3,5,9,8,10,6,11,4,7,12) ])

# Which group is it?
StructureDescription(g);
# "M12"

Size(g);
# 95040

Bra, det är alltså gruppen M12, dvs Mathieu-grupp av ordningen 12. Notera att det finns ett inbyggt kommando för att skapa en Mathieugrupp (MathieuGroup), men den har inte de generatorer som vil ska använda, alltså rullar vi vår egen.


Nu börjar det roliga. Låt oss som exempel ta följande sekvens som nyss skapats av M12-programmet.


#
# Create the puzzle to solve
#
puzzle:=[4, 5, 11, 1, 9, 6, 3, 10, 2, 7, 12, 8];;


För att få reda på lösningen görs en "faktorisering", med hjälp av funktionen Factorization.


Factorization(g, PermList(puzzle)^-1);
# x1*x2^2*x1*x2^-5*x1*x2^-5

Här har vi en lösning som ska tolkas som operationer i pysslet:

x1*x2^2*x1*x2^-5*x1*x2^-5

x1 betyder den första generatorn (dvs Reverse/Inverse) och x2 är Merge.

Det finns två saker att tänka på här:
- man ska läsa sekvensen baklänges
- alla operationer med negativ exponent måste konverteras till en positiv exponent. Det görs med en enkel subtraktion: x2^-5 innebär samma sak som x2^(11-5) = x2^6

Om vi översätter enligt ovanstående två regler blir det:

x2^6 x1 x2^6 x1 x2^2 x1

Så, uttolkat i samma form som M12-applikationen blir lösningen följande. Tänk på att vi arbetar med lösningen bakifrån och att x1 är I och x2 är M:

M6 I M6 I M2 I

Detta är en lösning med 6+1+6+1+2+1 = 17 steg.


En variant

Förutom Factorization finns det en annan metod, och det är den som generellt rekommenderas för att göra denna typ av "faktoriseringar". Tyvärr tenderar den att generera längre lösningar än med Factorization.


#
# This is the recommended function for factorizations, but it gives longer
# solutions (strings) than Factorization.
#

#
# Create names to identify the operations
#
M:=g.2; R:=g.1;
hom:=EpimorphismFromFreeGroup(g:names:=["R","M"]);

#
# Now, solve the puzzle
#
PreImagesRepresentative(hom,PermList(puzzle)^-1);
# M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2

Lösningen är alltså:

M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2

Notera att R^-1 ska tolkas som en Inverse-operation.

Ovanstående motsvarar följande M12-operationer:

M2 I M10 I M8 I M3 I M I M4 I M8

Detta är en lösning på 2 + 1 + 10 + 1 + 8 + 1 + 3 + 1 + 1 + 1 + 4 + 1 + 8 = 42 steg, vilket är mycket längre än Factorization-approachen.


Man bör notera att dessa faktoriseringar är optimerade att få så små exponenter som möjligt oavsett om det är positiva eller negativa exponenter. Vi är dock endast intresserade av positiva exponenter och lider därför av denna optimering.

Om man adderar exponenterna utan tecken, ger Factorization i alla fall en enklare lösning.

Factorization: x1*x2^2*x1*x2^-5*x1*x2^-5 = 1 + 2 + 1+ 5 +1+ 5 = 15 steg.

PreImagesRepresentative: M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2 = 3 + 1 + 4 + 1 + 1+ 3+ 1 + 3+ 1+ 1 + 1 + 2 = 22 steg.


Båda dessa faktoriseringar går mycket snabbt, typ någon sekund eller så.


Jämförelse med MiniZinc-lösningen
Jag testade att köra pysslet med MiniZinc-modellen M12.mzn. Den tar väldigt lång tid (typ 10-tals minuter) och ger följande lösning på 18 steg, dvs något sämre än Factorization-varianten. Operatorn 1 motsvarar Merge och operatorn 2 motsvarar Inverse.


2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2

dvs operationerna: R M6 R M2 R M R M3 R M

Så här ser sekvensen ut för respektive operation. Siffran till vänster är operationen. Första raden är ursprungssekvensen och är endast med för presentationens skull.


0: 4 5 11 1 9 6 3 10 2 7 12 8
2: 8 12 7 2 10 3 6 9 1 11 5 4
1: 8 7 10 6 1 5 4 11 9 3 2 12
1: 8 10 1 4 9 2 12 3 11 5 6 7
1: 8 1 9 12 11 6 7 5 3 2 4 10
1: 8 9 11 7 3 4 10 2 5 6 12 1
1: 8 11 3 10 5 12 1 6 2 4 7 9
1: 8 3 5 1 2 7 9 4 6 12 10 11
2: 11 10 12 6 4 9 7 2 1 5 3 8
1: 11 12 4 7 1 3 8 5 2 9 6 10
1: 11 4 1 8 2 6 10 9 5 3 7 12
2: 12 7 3 5 9 10 6 2 8 1 4 11
1: 12 3 9 6 8 4 11 1 2 10 5 7
2: 7 5 10 2 1 11 4 8 6 9 3 12
1: 7 10 1 4 6 3 12 9 8 11 2 5
1: 7 1 6 12 8 2 5 11 9 3 4 10
1: 7 6 8 5 9 4 10 3 11 2 12 1
2: 1 12 2 11 3 10 4 9 5 8 6 7
1: 1 2 3 4 5 6 7 8 9 10 11 12 % Solution!

Posted by hakank at juni 29, 2008 08:25 EM Posted to Constraint Programming | Matematik | Pyssel