Permutacje
18.11.2009 - Marcin Oczeretko
Z permutacjami spotykamy się dość często w informatyce, jak również i w codziennym życiu, choć czasem nawet nie zdajemy sobie z tego sprawy. Jeśli pragniesz dowiedzieć się, co kryje się za pojęciem permutacji i nieco sformalizować swoje intuicyjne do niego podejście, zapraszam do lektury poniższego artykułu. W ramach wprowadzenia zajmijmy się najpierw dość prostą grą. Chyba prawie każdy grał choć raz w Scrabble (niektórzy nawet twierdzą, że w większosci domów znajduje się pudełko z tą grą). Zasady nie są skomplikowane - w trakcie rozgrywki każdy z graczy dysponuje zestawem siedmiu płytek z nadrukowanymi nań literami i stara się ułożyć z nich jakieś słowo oraz dopasować je do płytek leżących już na planszy. Rozpatrzmy nieco uproszczoną wersję tej gry - mamy siedem płytek i musimy zbudować z nich wszystkich sensowny wyraz. Załóżmy, że posiadamy taki zestaw: Niektórzy być może zauważyli już, że możemy ułożyć za pomocą tych płytek wyraz MLECZNY. Ci, którym się to nie udało, nie muszą się zbytnio martwić. Wszystkich możliwych ustawień jest bardzo dużo, nic więc dziwnego, że jeden konkretny układ gdzieś nam umknął. Dla spokoju ducha policzmy jednak ile różnych wyrazów można ułożyć z tych siedmiu literek.
Literkę rozpoczynającą wyraz możemy wybrać na siedem sposobów, gdyż tyle płytek mamy do dyspozycji. Drugą pozycję uzupełniamy na jeden z sześciu sposobów (możemy przecież wybrać dowolną płytkę poza tą, która już jest na stojaku). Trzecią płytkę wybieramy spośród pięciu, itd. Widać już zatem, że wybierając i-tą literkę, mamy do wyboru płytek, bowiem wykorzystaliśmy już wcześniej. Za każdym razem otrzymujemy inny wyraz, więc wszystkich układów jest: . Jeśli więc nie zauważyłeś, że z CELMNYZ można ułożyć słowo MLECZNY, to pominąłeś jedną z 5040 kombinacji. Nie ma więc szczególnych powodów, by się tym faktem przejmować. Nietrudno pokazać, że gdybyśmy mieli rozróżnialnych płytek, to ilość różnych ich ustawień jest równa (przez , czyli "n silnia", oznaczamy iloczyn wszystkich liczb naturalnych od do ).
(9 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com