Strona główna » Algorytmy » Artykuły » Perfekcyjne Tasowanie
 

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:

Talia12345678
Po tasowaniu15263748

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:

Talia12345678
Tasowanie #115263748
Tasowanie #213572468
Tasowanie #312345678

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.

C++C#
Python
  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.

C++C#
Python
  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.

C++C#
Python
  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:

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

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:

Talia12345
Tasowanie #114253
Tasowanie #215432
Tasowanie #313524
Tasowanie #412345

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