Permutacja

Permutacja
Polecane artykuły
Algorytm genetyczny Indukcja eliminacyjna Drzewo decyzyjne Metody heurystyczne Metoda Blocha-Schmigalli Próba PERT GERT Model ekonometryczny

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.

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.

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.

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={a₁, a₂,..., a_n). 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:

P_n= n!

(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:

1. biały, czerwony, zielony
2. biały, zielony, czerwony
3. czerwony, biały, zielony
4. czerwony, zielony, biały
5. zielony, czerwony, biały
6. zielony, biały, czerwony

Możliwości jest sześć.

Korzystając ze wzoru na permutację bez powtórzeń otrzymamy ten sam wynik:

P₃= n! = 3! = 1 * 2 * 3 = 6

Permutacja z powtórzeniami

Niech A będzie zbiorem dowolnych k-elementów, A={a₁, a₂,..., a_k). 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ę n₁, n₂... n_k razy. (n = n₁+n₂+...+n_k)

Liczbę wszystkich możliwych permutacji n elementów zbioru A oblicza się na podstawie wzoru:

P_n= n! / n₁!...n_k!

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)

1. a₍₁₎ r a₍₂₎
2. a₍₂₎ r a₍₁₎
3. a₍₁₎ a₍₂₎ r
4. a₍₂₎ a₍₁₎ r
5. r a₍₁₎ a₍₂₎
6. r a₍₂₎ a₍₁₎

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:

P_n= n! / n₁!...n_k!

element a powtarza się 2 razy, a element r 1 raz, podstawiając do wzoru otrzymujemy:

P₃= 3! / 1!2! = 1*2*3 / 1*2 = 3

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.

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
• Hellwing Z. (1998). Elementy rachunku prawdopodobieństwa i statystyki matematycznej, Warszawa
• Krysicki W., Bartos J., Dyszka W., Królikowska K., Wasilewski M. (1999). Rachunek prawdopodobieństwa i statystyka matematyczna w zadaniach, 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

Przypisy

Autor: Paulina Kiwior, Arkadiusz Krzeszowiec