Permutacja
| Permutacja |
|---|
| Polecane artykuły |
Permutacją zbioru A składającego z się z n-elementów, określamy każdy n-wyrazowy ciąg, zawierający wszystkie elementy zbioru A.
Permutacja to każde możliwe uporządkowanie wszystkich elementów zbioru.
Pamiętaj:Jeśli w zadaniu wykonujemy operacje na wszystkich elementach zbioru i istotna jest ich kolejność to korzystamy z permutacji.
TL;DR
Permutacja to uporządkowanie elementów w zbiorze. Od dawna była badana w matematyce. Istnieją permutacje bez powtórzeń, gdzie każdy element występuje tylko raz, i permutacje z powtórzeniami, gdzie elementy mogą się powtarzać. Liczbę możliwych permutacji można obliczyć za pomocą odpowiednich wzorów. Permutacje mają wiele zastosowań, takich jak w algorytmach wykrywania błędów.
Historia
Reguła określania liczby permutacji n elementów była znana w kulturze indyjskiej co najmniej około 1150 roku, indyjski matematyk Bhaskara II wspominał o tym:
Iloczyn ciągu arytmetycznego, rozpoczynającego się i wzrastającego przez jedność, a kończącego na liczbie miejsc, będzie wariacją liczby z określonymi cyframi[1].
Fabian Stedman w roku 1677 opublikował książkę Campanologia. Wyjaśniał w niej różne metody wydzwaniania permutacji na dzwonach. Zaczynając od dwóch dzwonów: "pierwszy i drugi można przedstawić na dwa sposoby", co ilustruje pokazując 1 2 i 2 1. Następnie wyjaśnia, że za pomocą trzech dzwonów są "trzy razy dwie liczby, które mają być stworzone z trzech", co ponownie zostało zilustrowane. Jego wyjaśnienie obejmuje "odrzuć 3, a 1.2 pozostanie, odrzuć 2, a 1.3 pozostanie, odrzuć 1, a 2.3 pozostanie". Następnie przechodzi do czterech dzwonów i powtarza metodę odrzucania, pokazując, że będą cztery różne zestawy po trzy. Jest to proces rekurencyjny. Kontynuuje z pięcioma dzwonami za pomocą metody odrzucania i zestawia uzyskane 120 kombinacji. W tym momencie poddaje się i zauważa:
Natura tych metod jest taka, że zmiany na jednej liczbie powodują zmiany na wszystkich mniejszych liczbach,... o tyle, że wydaje się, że całkowite uderzenia zmian jednej liczby powstaje przez połączenie całkowitych uderzeń na wszystkich mniejszych liczbach w jedno całe ciało.
Stedman rozszerzał rozważanie permutacji. Następnie zajął się liczbą permutacji liter alfabetu i koni z 20 stajni[2].
Pierwszy przypadek, w którym pozornie niepowiązane pytania matematyczne badano za pomocą permutacji, miał miejsce około 1770 roku, kiedy Joseph Louis Lagrange zauważył, że właściwości permutacji równań wielomianów są związane z możliwościami ich rozwiązań. Doprowadziło to później do opracowania swojej teorii Évariste Galois, która daje pełny opis tego, co jest możliwe i niemożliwe w odniesieniu do rozwiązywania równań wielomianowych przez pierwiastki. We współczesnej matematyce jest wiele podobnych sytuacji, w których zrozumienie problemu wymaga zbadania związanych z nim pewnych permutacji.
Permutacja bez powtórzeń
Niech A będzie zbiorem dowolnych n-elementów, A={a1, a2,..., an). Permutacją bez powtórzeń n-wyrazowego zbioru A określamy każdy n-elementowy ciąg, w którym wszystkie składniki zbioru A występują tylko raz.
Liczbę wszystkich możliwych permutacji n elementów zbioru A oblicza się na podstawie wzoru:
(n!= 1 * 2 *... * (n-2)*(n-1)*n)
Przykład
Przypuśćmy, że mamy zbiór trzech kolorów:
A=(biały, czerwony, zielony)
zatem nasz zbiór posiada 3 elementy (n=3). Zakładając, że żaden z kolorów nie może się powtarzać, możliwe permutacje (możliwości rozstawienia kolorów) są następujące:
- biały, czerwony, zielony
- biały, zielony, czerwony
- czerwony, biały, zielony
- czerwony, zielony, biały
- zielony, czerwony, biały
- zielony, biały, czerwony
Możliwości jest sześć.
Korzystając ze wzoru na permutację bez powtórzeń otrzymamy ten sam wynik:
Permutacja z powtórzeniami
Niech A będzie zbiorem dowolnych k-elementów, A={a1, a2,..., ak). Permutacją z powtórzeniami k-wyrazowego zbioru A określamy każdy k-elementowy ciąg, w którym wszystkie składniki zbioru A powtarzają się n1, n2... nk razy. (n = n1+n2+...+nk)
Liczbę wszystkich możliwych permutacji n elementów zbioru A oblicza się na podstawie wzoru:
Przykład
Przypuśćmy, że mamy zbiór trzech liter:
A=(a, r, a)
zatem nasz zbiór posiada 3 elementy (k=3). Zakładając, że każdy z kolorów może się powtarzać, możliwe permutacje (możliwości rozstawienia liter) są następujące:
(żeby rozróżnić literki a, w nawiasach przyporządkowano im numer)
- a(1) r a(2)
- a(2) r a(1)
- a(1) a(2) r
- a(2) a(1) r
- r a(1) a(2)
- r a(2) a(1)
Możliwości jest sześć, jednak należy zauważyć, że słowa się powtarzają po dwa razy. Zatem faktycznie możliwości będzie jedynie trzy ala, laa i aal.
Do obliczenia korzystniej zatem skorzystać ze wzoru na permutację z powtórzeniami:
element a powtarza się 2 razy, a element r 1 raz, podstawiając do wzoru otrzymujemy:
Zastosowanie
Permutacje są wykorzystywane jako składnik algorytmów wykrywania i korekcji błędów, takich jak turbo kody, na przykład standard mobilnej telekomunikacji 3GPP Long Term Evolution (LTE) wykorzystuje te pomysły. Takie zastosowania podnoszą kwestię szybkiego generowania permutacji spełniających określone wymagane właściwości[3].
Przypisy
Bibliografia
- Biggs N. L. (1979). The Roots of Combinatorics, "Historia Math"
- Dolev S., Lahiani L., Haviv Y. (2013). Unique permutation hashing, "Theoretical Computer Science" Department of Computer Science, Ben-Gurion University
- Hellwig Z. (1998), Elementy rachunku prawdopodobieństwa i statystyki matematycznej , Wydawnictwo Naukowe PWN, Warszawa
- Krysicki W., Bartos J., Dyczka W., Królikowska K., Wasielewski M. (1999), Rachunek prawdopodobieństwa i statystyka matematyczna w zadaniach, Wydawnictwo Naukowe PWN, Warszawa
- Stedman F. (1677). Campanalogia, W.S. London
- Wąsik J. (2009). Złamanie szyfru Enigmy przy użyciu teorii permutacji, Instytut Matematyki Wydział Matematyki i Informatyki Uniwersytet Jagielloński
Autor: Paulina Kiwior, Arkadiusz Krzeszowiec
