Kombinator ;)
Posted in C#, Programowanie on Luty 11th, 2006 by Tomasz Cudok – 1 CommentNie tak dawno temu, podczas przerabiania rachunku prawdopodobieństwa, nauczyciel dał nam do rozwiązania dość trudne zadanie na dodatkową ocenę. Przysiadłem do niego w domu i nie mogąc nic wymyślić, postanowiłem rozwiązać je metodą brute-force. Napisałem na szybko programik, który generował permutacje danego zbioru, każdy z otrzymanych w ten sposób zbiorów sprawdzałem pod kątem odpowiednich kryteriów w pętli i w ten sposób wynik znalazł się sam. Następnego dnia poszedłem się pochwalić nauczycielowi i zostałem mile zaskoczony. Otóż mój nauczyciel matematyki również lubi dłubać w kodzie. I tym sposobem dostałem zadanie specjalne – napisać program generujący permutacje, kombinacje, wariacje (z powtórzeniami i bez) podanego zbioru (max. 10 elementów). Jako, że zadanie było ciekawe, wziołem się za nie niemal natychmiast.
Oczywiście wybór platformy nie był trudny. Bez wahania wybrałem .NET i C#. Program napisałem w darmowym Visual C# Express 2005 Microsoftu. Główną trudnością było opracowanie w miare wydajnych algorytmów mutujących zbiory. Jednak szybko okazało się, że dużym problemem jest też wyświetlenie listy z milionem elementów. Tak więc przy dużych ilościach wynikowych zbiorów program upomina się o bezpośredni zapis do pliku, co jest zdecydowanie bardziej wydajne. W ten sposób, na moim sprzęcie, można sobie utworzyć plik ze wszystkimi permutacjami zbioru 10 elementowego (jest ich 10! = 3628800) w nieco ponad minutę. A algorytm permutacji można by pewnie sporo zoptymalizować, ponieważ jest on… rekurencyjny (lenistwo wzieło górę…).
Niby prosty programik, a dzięki niemu nabyłem całkiem sporo doświadczenia w programowaniu aplikacji okienkowych pod Windowsa. Wytworzyłem sobie styl nazewnictwa kontrolek, doświadczyłem na własnej skórze, że zaprojektowanie ładnego GUI nie jest wcale takie proste jak się może wydawać, przyswoiłem sobie parsowanie dokumentów XML w .NET. A przy okazji nauczyłem się na pamięć wzorów na obliczenie ilości wyników poszczególnych operacji kombinatorycznych. Uwielbiam łączyć przyjemne z pożytecznym 
Program do działania wymaga zainstalowania .NET Framework 2.0.