O permutacjach i ich teoretycznie możliwej roli w akcie stworzenia świata już rozmawialiśmy – patrz poprzednia notka. Od teorii czas przejść do praktyki i popermutować samemu. No, może nie tyle samemu ile z pomocą – maszyny liczącej. Są różne maszyny i różnymi językami można z nimi rozmawiać. Przy rozmowie z maszyną przydaje się tłumacz. Tłumacz tłumaczy nasze życzenia na komendy, które maszyna rozumie. A jak maszyna już nasze komendy zaakceptuje i obrobi, znów przez tłumacza dowiadujemy się o wynikach – w języku dla nas zrozumiałym.
Za tłumacza wybrałem tym razem powszechnie dostępny program Maxima. Objętościowo stosunkowo niewielka, po rozpakowaniu zajmuje na dysku nieco ponad 100 MB. Jest dostępna zarówno pod Windows jak i pod Linux (Mac też). Każdy może ją sobie ściągnąć i zainstalować – wedle chęci i wedle wymagań.
Maxima może wiele, ale my przyjrzymy się jedynie temu jak z Maximą można rozmawiać o permutacjach i o geometrii Fano. Maxima jest napisana w języku Lisp, języku dziś niemal zarzuconym. Stąd też szybkość jej działania nie jest zachwycająca. Nie mniej, jak na nasze potrzeby, wystarczająca.
Chcę wyliczyć, przy pomocy Maximy wszystkie symetrie geometrii Fano, podobnie jak liczyliśmy te symetrie dla geometrii trójkąta w notce poprzedniej. Najpierw więc musimy wygenerować macierze permutacji dla liczb (1,2,...,7). Permutacji tych będzie 7! = 5040, i tyleż musimy wygenerować macierzy permutacji. Macierz permutacji to, w naszym przypadku, macierz o siedmiu wierszach i siedmiu kolumnach. W każdym wierszu i w każdej kolumnie jest dokładnie jedna jedynka, pozostałe to zera.
Szczęśliwie Maxima wie jak generować permutacje. Najpierw definiujemy funkcję, nazwę ją p7:
p7() := permutations([1,2,3,4,5,6,7])$
Po napisaniu powyższej komendy w linii, naciskamy Shift-Enter. Wtedy Maxima oblicza i wyrzuca wynik, lub komunikuje „done” (zrobione), lub też, jeśli jest to tylko definicja, przechodzi do następnej linii. Składnia Maximy jest raczej nietypowa, oswojenie się z nią wymaga pewnego czasu – mi zajęło to dwa dni. Z sieci można ściągnąć kilka tutoriali w języku polskim. Na przykład krótki opis Maximy mojego znajomego z Wrocławia, Zbigniew Kozy:
Maxima – Algebra symboliczna na komputerze
Maxima – Część II. Równania
Można też sobie ściągnąć wykładzik „Maxima – przewodnik praktyczny” Rafała Topolnickiego (też z Wrocławia)
Następnie tworzymy listę p7l wszystkich permutacji:
p7l: full_listify (p7())$
Możemy sprawdzić jej długość:
length (p7l);
Maxima odpowie nam: 5040
Możemy sprawdzić jak wygląda dwusetna permutacja:
p7l[200];
Odpowiedź brzmi: [1,3,6,4,2,7,5]
W istocie, jest to jedno z przestawień ciągu liczb 1,2,3,4,5,6,7.
Teraz chcemy dla każdej permutacji zbudować odpowiednią macierz permutacji. Będziemy mieć tych macierzy 5040, każda z nich będzie 7x7. Więc najpierw utwórzmy tabelę, oznaczę ją literą g, 5040 macierzy z samymi zerami:
for k:1 thru length(p7l) do g[k]: zeromatrix(7,7)$
Sprawdzamy jak wygląda, powiedzmy, piaty element tej tabeli:
g[5];
Maxima odpowiada wyrzucając na macierz z budowaną z samych zer – jak chcieliśmy.
Teraz, dla każdej z 5040 permutacji musimy zastąpić niektóre z tych zer jedynkami. Nie będę tłumaczył dlaczego tak się robi, choć zrozumieć samemu, jak się zobaczy ko, łatwo:
for k:1 thru length(p7l) do
for l:1 thru 7 do g[k][l,p7l[k][l]]: 1$
Wykonanie tego kodu trwa kilka sekund. Maxima działa w trybie interpretacji, jest więc powolna. Sprawdzamy np. g[100]
Faktycznie, jest to macierz permutacji. Mamy więc już tabelkę 5040 macierzy permutacji.
Teraz tworzymy macierz incydencji dla geometrii Fano – nazwę ją M. Podałem ją w komentarzu do poprzedniej notki. Teraz przepisuję ją w języku Maximy:
M: matrix (
[1,0,0,0,1,0,1],
[1,1,0,0,0,1,0],
[0,1,1,0,0,0,1],
[1,0,1,1,0,0,0],
[0,1,0,1,1,0,0],
[0,0,1,0,1,1,0],
[0,0,0,1,0,1,1]
);
Chcemy teraz permutować, niezależnie, wiersze i kolumny macierzy M i sprawdzać dla jakich permutacji macierz M po takiej permutacji przechodzi w siebie. W notce Geometryczne wyliczanki-tasowanki pisałem:
Teraz pozostaje jedynie wymnożenie naszej macierzy incydencji M przez macierze tasujące P, z lewej i z prawej i zobaczenie kiedy macierz M się przy takim mnożeniu nie zmienia. Innymi słowy, jeśli nasze sześć macierzy tasujących oznaczę przez P(i), i=1,2,3,4,5,6, to chcę znaleźć te pary (i,j) przy których
P(i).M.P(j) = M
(Kropką oznaczam mnożenie macierzy) Zrobiłem tambłąd. Błąd zrobiłem zresztą wcześniej. Permutujemy wiersze macierz M mnożąc przez macierz permutacji z lewej – to prawda. Ale by przepermutować kolumny,trzeba pomnożyć z prawej nie przez P, a przez P transponowane.
Chcemy więc sprawdzić dla jakich par (i,j) będzie zachodzić równość:
P(i).M.transpose(P(j)) = M
No i ciekawi nas ile takich będzie. Każda taka para oznacza bowiem jedną z symetrii naszej geometrii.
By Maxima zrozumiała, że porównujemy dwie macierze używamy specjalnej składni. Na przykład sprawdźmy czy macierz M jest równa sobie samej:
is(equal(M,M));
Maxima odpowiada „true”, że niby to prawda. Testujemy dalej:
is(equal(P[2].M.transpose(P[2]),M));
Maxima odpowiada „false” - nieprawda.
Sprawdźmy więc teraz ile będzie symetrii w których wiersze przestawiamy tak samo jak kolumny. Musimy w tym celu wykonać 5040 porównań. Nie jest to liczba ogromna, więc nawet Maximie nie powinno zająć to wiele czasu. Do liczenia trafień użyję wskaźnika i, któremu na początek nadaję wartość zero:
i: 0;
Przy każdym trafieniu będę zwiększał wartość i o jeden i kazał pisać Maximie numer permutacji dla której nastąpiło trafienie:
for k:1 thru 5040 do
if is(equal(P[k].M.transpose(g[k]),M)) then (i:i+1,print(k));
Po kilku sekundach Maxima wypluwa:
1
874
1745
2611
3457
4201
4321
Mamy więc siedem symetrii tego rodzaju. Na wszelki wypadek pytamy o aktualną wartość wskaźnika i:
print(i);
Maxima odpowiada: 7. Nie dziwimy się zbytnio, bowiem nasza macierz incydencji była spisywana z modelu jawnej siedmiokrotnej symetrii.
Teraz przychodzi czas na robotę prawdziwą. Musimy bowiem dokonać 5040x5040, czyli ponad 25 milionów porównań. Ostrzegam więc: na moim komputerze wykonanie następnej komendy zajęło 40 minut. Pracowały przy tym trzy z jądra procesora. Oczywiście mógłbym nad całością popracować, postarać się zapisać cały program tak, bym mógł go skompilować. Pewnie zajęłoby mi to cały dzień, a rezultat byłby taki, że po całym dniu pracy, Maxima wykonałaby program w 4 minuty miast w 40 minut. Odpuszczam to.
Oto mały blok programowy, który wykonuje nasze zadanie:
block([l],
l: 0,
for i:1 thru 5040 do
for j:1 thru 5040 do
if is(equal(P[i].M.transpose(P[j]),M)) then
(l:l+1,print(i,j),tab[l]:[i,j]));
Wskaźnik l jest tu zmienną wewnętrzną w bloku, numerującą kolejne sukcesy. Wynikiem tego bloku jest tabela tab, której kolejne elementy to pary (i,j) dla których nastąpiło trafienie.
Jak wspomniałem wykonanie bloku zajmuje kilkadziesiąt minut, warto więc wynik zapisać do pliku:
write_data(tab,"C:/fano_sym.txt");
Nasz plik wygląda tak:
1 1 1
2 56 30
3 83 515
4 108 537
5 142 4554
6 168 4632
7 187 4507
8 213 4669
9 267 135
…..
168 5023 4109
Chcemy wiedzieć ile symetrii nam w końcu wyszło:
last(arrayinfo(tab));
Odpowiedź brzmi: 168
Dla ciekawych udostępniam całość mojego kodu. Można go wczytać do programu i realizować komórka po komórce przez Shift-Enter. Zwracam uwagę na dwie użyteczne operacje w oknie Maxima:
„Maxima/Restart Maxima”, oraz „Cell/Remove All Output”. Resztę można doczytać z licznych przewodników, oraz z „Reference manual”.
