Perfekcyjne Tasowanie

Algorytm

Perfekcyjne Tasowanie polega na podzieleniu talii kart na dwie, równe połowy, a następnie wstawienie kart z drugiej połowy do pierwszej w taki sposób, że pierwsza karta z drugiej połowy jest po pierwszej karcie z pierwszej i tak dalej dla każdej kolejnej pary kart. Przykładowo:

Jak można zauważyć pierwszy i ostatni element w takim tasowaniu nie zmieniają pozycji. W tablicy wynikowej zgodnie z algorytmem tasowania elementy na indeksach nieparzystych są z pierwszej połowy tablicy wejściowej, a z parzystych z drugiej połowy. Należy oczywiście pamiętać, że algorytm ten pasuje jedynie do tablic o parzystej długości!

Tasowanie kilka razy

Okazuje się, że dla określonej liczby kart w talii po k tasowaniach uzyska się oryginalny układ elementów w talii. Jednak dla różnej ilości kart możliwe, że będzie potrzebna inna ilość tasowań. Za każdym razem tasowanie jest wykonywane opisywanym algorytmem. Kontynuując podany wcześniej przykład otrzymujemy:

W przypadku talii o n = 8 kartach otrzymujemy oryginalny układ kart w tablicy. Jak się jedna okazuje dla 6 kart potrzeba, aż 4 tasowań czyli tyle samo co dla 16 kart. Jednak dla talii o 12 elementach trzeba powótrzyć tasowanie, aż 10 razy! Najbardziej odporna na tasowanie jest oczywiście talia złożona z dwóch kart, gdzie po jednym tasowaniu otrzymujemy.. to samo ułożenie.

Implementacja

Tasowanie

Poniższa funkcja perfekcyjneTasowanie() przyjmuje jako argument listę liczb, a jako wynik zwraca tą listę potasowaną zgodnie z algorytmem tasowania perfekcyjnego. Werjściowa tablica nie jest modyfikowana.

1. def perfekcyjneTasowanie(v):
2.   w = []
3.   polowa = int(len(v) / 2)
4.   for i in range(polowa):
5.     w.append(v[i])
6.     w.append(v[polowa + i])
7.   return w

Przedstawiony algorytm na początku deklaruje nową liste, a następnie dla każdej pary liczb (z dwóch różnych połówek) dodawane są do nowej listy. Na koniec zwracana jest nowa lista.

Testowanie funkcji

W celu przetesowania funkcji wystarczy poniższy fragment kodu. Należy pamiętać, że zarówno ten kod jak i napisana funkcja nie sprawdzają poprawności danych wejściowych czyli np. czy przekazana długość tablicy jest parzysta.

1. n = int(input("Ile jet kart?\n n = "))
2. v = []
3. for i in range(n):
4.   v.append(i)
5. w = perfekcyjneTasowanie(v)
6. for i in range(n):
7.   print(w[i], end=' ')

Ile tasowań?

Korzystając z przygotowanej wyżej funkcji perfekcyjneTasowanie() można napisać funkcję ileTasowan(), która zwróci ile razy trzeba przetasować listę, aby otrzymać z powrotem oryginalną listę. W tym jednak przypadku jako argument podawany jest jedynie ilość elementów, a nie ich konkretne wartości.

1. def ileTasowan(n):
2.   ile = 0
3.   v = []
4.   for i in range(n):
5.     v.append(i)
6.   pokolei = False;
7.   while (not pokolei):
8.     ile += 1
9.     v = perfekcyjneTasowanie(v)
10.     pokolei = True;
11.     for i in range(n):
12.       if (v[i] != i):
13.         pokolei = False
14.         break
15.   return ile

Na podstawie przekazanej wartości n funkcja sama generuje tablicę do potasowania. Zaletą takiego rozwiązania jest uproszczony system sprawdzania czy otrzymano z powrotem tablicę wejściową, ponieważ wszystkie elementy w tablicy to kolejne liczby nieujemne, więc wystarczy sprawdzić, że na i-tej pozycji jest wartość i.

Testowanie funkcji

W celu przetestowania kodu wystarczy wczytać od użytkownika liczbę i wypisać wynik:

1. n = int(input("Ile jet kart?\n n = "))
2. print(ileTasowan(n))

• Kod źródłowy Tasowanie
• Kod źródłowy Ile tasowań?

Zadania

Zadanie 1

Rozszerzmy definicję perfekcyjnego tasowania i przyjmijmy, że możn tasować tablice o nieparzystej liczbie elementów. Przykładowo jeśli mamy posortować tablice o 2n+1 elementach to w pierszej części będzie ich n + 1, a w drugiej n. Elementy drugiej tablicy powinny znaleźć się pomiędzy kolejnym parami elementów z tablicy pierwszej. Przykładowo dla n = 5:

Napisz funkcję perfekcyjneTasowanie() oraz ileTasowan() dla nowej definicji tasowania. Przetestuj napisane funkcje.

• Kod źródłowy Zadanie 1