A GAP programozási nyelv

Rubik kocka analizáló példaprogram

Rubik kocka analizáló példaprogram

Tekintsük a csoportjait a Rubik kockának, ha az kocka így néz ki:

					 +--------------+
                     |              |
                     |  1    2    3 |
                     |              |
                     |  4  top    5 |
                     |              |
                     |  6    7    8 |
                     |              |
      +--------------+--------------+--------------+--------------+
      |              |              |              |              |
      |  9   10   11 | 17   18   19 | 25   26   27 | 33   34   35 |
      |              |              |              |              |
      | 12  left  13 | 20 front  21 | 28 right  29 | 36  rear  37 |
      |              |              |              |              |
      | 14   15   16 | 22   23   24 | 30   31   32 | 38   39   40 |
      |              |              |              |              |
      +--------------+--------------+--------------+--------------+
                     |              |
                     | 41   42   43 |
                     |              |
                     | 44 bottom 45 |
                     |              |
                     | 46   47   48 |
                     |              |
                     +--------------+

A csoport az alábbi utasítással adható meg, amely megfelel a kocka oldalainak.

gap> cube := Group( > ( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19), > ( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35), > (17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11), > (25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24), > (33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27), > (41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40) );

Először is kérjük, a csoport méretét.

gap> Size( cube ); 43252003274489856000

Ennél kicsit többet fog mondani, ha faktorizáljuk ezt a számot. A kapott kifejezés ezt jelenti: 2^27 * 3^14 * 5^3 * 7^2 * 11.

gap> Collected( Factors( last ) ); [ [ 2, 27 ], [ 3, 14 ], [ 5, 3 ], [ 7, 2 ], [ 11, 1 ] ]

Vizsgáljuk meg a 48 pontú csoport működését. (Ehhez csökkentsük le a képernyőmértetét.)

gap> SizeScreen( [71, ] );; gap> orbits := Orbits( cube, [1..48] ); [ [ 1, 3, 17, 14, 8, 38, 9, 41, 19, 48, 22, 6, 30, 33, 43, 11, 46, 40, 24, 27, 25, 35, 16, 32 ], [ 2, 5, 12, 7, 36, 10, 47, 4, 28, 45, 34, 13, 29, 44, 20, 42, 26, 21, 37, 15, 31, 18, 23, 39 ] ]

Az első listában találhatóak a csúcsokon levő pontok, a másodikban az éleken lévőek, nyilván a két halmaz diszjunkt, hiszen egy Rubik kockán nem vihető át egy sarok egy élre.

Vizsgáljuk meg a csúcsokat, ehhez előbb traszfolmáljuk át őket az [1..24] intvervallumra.

gap> cube1 := Action( cube, orbits[1] ); gap> NrMovedPoints( cube1 ); 24 gap> Size( cube1 ); 88179840

Nos, eza csoprt nyilván tranzitív, nézzük meg, hogy primitiv-e!?

gap> corners := Blocks( cube1, MovedPoints( cube1 ) ); [ [ 1, 7, 22 ], [ 2, 14, 20 ], [ 3, 12, 16 ], [ 4, 17, 18 ], [ 5, 9, 21 ], [ 6, 10, 24 ], [ 8, 11, 23 ], [ 13, 15, 19 ] ]

Ez az nyolc blokk felel meg a kocka sarkainak. Nyilvánvalóan ezt a nyolc sarkot kell megvizsgálnunk. Az alábbi utasítás egy homomorf permutációjukat adja.

gap> blockhom1 := ActionHomomorphism( cube1, corners, OnSets ); <action homomorphism> gap> cube1b := Image( blockhom1 ); Group([ (1,2,4,3), (1,3,6,5), (1,5,8,2), (3,4,7,6), (5,6,7,8), (2,8,7,4) ]) gap> Size( cube1b ); 40320

A permutáció csoport foka 8, rendje 40320, tehát ez egy szimmetrikus csoport 8 ponttal: S(8). Ezután nézzük meg a csoport magját.

gap> Factors( Size( Kernel( blockhom1 ) ) ); [ 3, 3, 3, 3, 3, 3, 3 ] gap> IsElementaryAbelian( Kernel( blockhom1 ) ); true

Megmutatható, hogy ez egy Ábel-csoport, és ez a csoport és a mag generálja az eredeti kockát.

gap> cmpl1 := Complementclasses( cube1, Kernel( blockhom1 ) ); [ Group([ (1,3,4,2)(7,16,17,14)(12,18,20,22), (1,2,3,4,5,6,13)(7,14,16,17,21,10,15)(9,24,19,22,20,12,18), (1,2,3,4,5,8,13)(7,14,16,17,21,23,15)(9,11,19,22,20,12,18) ]) ] gap> cmpl1 := cmpl1[1];; gap> Size( cmpl1 ); 40320

Ellenőrizzük a komplementer tulajdonságait:

gap> Size( Intersection( cmpl1, Kernel( blockhom1 ) ) ); 1 gap> ClosureGroup( cmpl1, Kernel( blockhom1 ) ) = cube1; true

Van erre elegánsabb módszer is:

gap> IsBijective( RestrictedMapping( blockhom1, cmpl1 ) ); true

Valójában tudjuk, hogy a kocka egy alcsoport. Ez azt fejezi ki, hogy a csúcsokat nem forgathatjuk szabadon, azaz egyik csúcs óramutató írányú elfogratása esetén egy másikat kell ellenkező írányba fogratnunk. Ezt fejezik ki a következő teszetek.

gap> (1,7,22) in cube1; false gap> (1,7,22)(2,20,14) in cube1; true

Többé-kevésbé ugyanazok történnek, ha az éleket vizsgáljuk.

gap> cube2 := Action( cube, orbits[2] );; gap> Size( cube2 ); 980995276800 gap> edges := Blocks( cube2, MovedPoints( cube2 ) ); [ [ 1, 11 ], [ 2, 17 ], [ 3, 19 ], [ 4, 22 ], [ 5, 13 ], [ 6, 8 ], [ 7, 24 ], [ 9, 18 ], [ 10, 21 ], [ 12, 15 ], [ 14, 20 ], [ 16, 23 ] ] gap> blockhom2 := ActionHomomorphism( cube2, edges, OnSets );; gap> cube2b := Image( blockhom2 );; gap> Size( cube2b ); 479001600 gap> Factors( Size( Kernel( blockhom2 ) ) ); [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ] gap> IsElementaryAbelian( Kernel( blockhom2 ) ); true gap> cmpl2 := Complementclasses( cube2, Kernel( blockhom2 ) );; gap> Length( cmpl2 ); 4

Végül a következő teszetek, is azt mutatják, hogy ha egy élt megfordítunk, akkor egy másik is átfordul.

gap> (1,11) in cube2; false gap> (1,11)(2,17) in cube2; true

A cube1 és a cube2 leírja a cube műveleteit. Egyértelmű, hogy a kocka ezen csoprtok egy alcsoportja. Hasonlítsuk össze a két csoport szorzatát, és az eredeti csoportot. Látszik, hogy utóbbi a 2 indexű alcsoportja.

gap> Size( cube ); 43252003274489856000 gap> Size( cube1 ) * Size( cube2 ); 86504006548979712000

A hiányzó 2 index arra utal, hogy nem engedhetünk meg minden műveletet a kockán.

gap> (17,19)(11,8)(6,25) in cube; false gap> (7,28)(18,21) in cube; false gap> (17,19)(11,8)(6,25)(7,28)(18,21) in cube; true

Végül nézzük meg a centrumát a kocka csoportnak. Láthatjuk, hogy eg nem triviális elemet fog tartalmazni a lista, mégpedig azt, hogy mind a tizenkét él egyszerre van megfordítva.

gap> z := Centre( cube ); Group( [ (2,34)(4,10)(5,26)(7,18)(12,37)(13,20)(15,44)(21,28)(23,42)(29, 36)(31,45)(39,47) ])

Végül nézzük meg azokat a transzformáció sorozatokat, amelyek visszaállítják a kockát az eredeti helyzetbe. Erre a célra be kell vezetni egy szabad csoportot, és egy homomorfizmust.

gap> f := FreeGroup("t","l","f","r","e","b"); gap> hom := GroupHomomorphismByImages( f, cube, GeneratorsOfGroup(f), > GeneratorsOfGroup(cube) ); [ t, l, f, r, e, b ] -> [ (1,3,8,6)(2,5,7,4)(9,33,25,17)(10,34,26,18)(11,35,27,19), (1,17,41,40)(4,20,44,37)(6,22,46,35)(9,11,16,14)(10,13,15,12), (6,25,43,16)(7,28,42,13)(8,30,41,11)(17,19,24,22)(18,21,23,20), (3,38,43,19)(5,36,45,21)(8,33,48,24)(25,27,32,30)(26,29,31,28), (1,14,48,27)(2,12,47,29)(3,9,46,32)(33,35,40,38)(34,37,39,36), (14,22,30,38)(15,23,31,39)(16,24,32,40)(41,43,48,46)(42,45,47,44) ]

Először is dekomponáljuk a centrum elemeit.

gap> PreImagesRepresentative( hom, z.1 ); l^-1*t^-1*e^-1*t^2*e*l*f*r*t^-1*r^-1*f^-1*t*f*r*t*r^-1*t^-1*f^-1*t^ -1*f*t*l*t*l^-1*f^-1*l*t^-1*l^-1*f*r*t^-1*r^-1*f^-1*l*t*f*t^-1*f^ -1*l^-1*t*f^-1*l^-1*t^-1*l*t*f*t^-2*f*t*f^-1*t^-1*l^-1*t^-1*l*t^-1*l^ -1*t*e^-1*t*e*l*t*l*t*e*l^-1*e^-1*t^-1*l^-3*b*f*b^-1*l^-1*f^-1*t*l^ -1*f*t*f*l^-1*t^-1*b*r^-1*b^-1*t^-2*e^-1*r*e*r*f^-1*e*t^-1*e^-1*r^ -2*t^-2*l^-1*b^-1*r^-1*e^-1 gap> Length( last ); 106

Aztán dekomponálunk pár általunk választott tetszőleges elemet.

gap> PreImagesRepresentative( hom, (17,19)(11,8)(6,25)(7,28)(18,21) ); l^-1*t^-1*l*f*r*t*r^-1*f^-1*l*t*f*t^-1*f^-1*l^-1*t^2*f*t*l*t*l^-1*f^ -1*l*t^-1*l^-1*f*t^-1*f^-1*l*t*l^-1*t*l*t^-2*l^-1*f*t*r*t^-1*r^ -1*t*r*t^-1*r^-1*f^-1*t*l*f^-1*l^-1*f*l^-1*t^-1*l*t^-2*f*t*f^-1*l^ -1*f^-1*l^-2*f*l*e^-1*t*e*l*t^-1*e^-1*t^-1*e*l*b*f^-1*b^-1 gap> Length( last ); 77

Leellenőrizhetjük, hogy dekompozíció helyes-e.

gap> Image( hom, pre ); (1,43,6,27,32,46)(2,4,13,34,10,20)(3,38,40,9,24,17)(5,15,45,23,29,47, 26,44,31,42,36,39)(7,18)(8,22)(11,33,48,14,35,30)(12,21,37,28)(16, 19)(25,41) gap> last = r; true