Kapitola 9: Pokročilé seznamy – Třídění a manipulace

Představte si, že máte v ruce balíček karet, ale jsou úplně zpřeházené. Nebo máte seznam skóre hráčů, ale nevíte, kdo vyhrál, protože nejsou seřazená. Seznamy jsou mocné, ale často v nich vládne chaos. V této kapitole se naučíme, jak tento chaos zkrotit. Naučíme se seznamy třídit a manipulovat s nimi jako profesionálové. Třídění je jedním ze základních kamenů informatiky – pokud umíte efektivně třídit data, umíte vyřešit spoustu problémů.

9.1 Vestavěné predikáty – Nástroje v kufříku

Než začneme psát vlastní složité algoritmy, podíváme se do kufříku nástrojů, které nám Prolog nabízí. Jsou to vestavěné predikáty, které už někdo chytře naprogramoval za nás.

• append(Seznam1, Seznam2, Vysledek): Spojí dva seznamy dohromady. Je to "švýcarský nůž" Prologu, protože umí seznamy nejen spojovat, ale i rozdělovat! (Zkuste se zeptat append(X, Y, [1,2,3]).).
• member(Prvek, Seznam): Zjistí, zda je prvek v seznamu. To už známe, ale Prolog to má v sobě.
• select(Prvek, Seznam, Zbytek): Vybere prvek ze seznamu a vrátí zbytek. Skvělé pro karetní hry (líznutí karty).
• permutation(Seznam, Permutace): Vytvoří všechny možné varianty seřazení seznamu (anagramy).

9.2 Třídění (Bubble Sort) – Bublinky ve vodě

Třídění je klasický problém. Jak seřadit čísla od nejmenšího po největší? Zkusíme si napsat Bubble Sort (Bublinkové třídění). Princip je jednoduchý a elegantní: představte si bublinky ve vodě. Větší (těžší) bublinky stoupají pomaleji, menší (lehčí) rychleji. Pokud jsou dva prvky vedle sebe špatně (větší je před menším), prohodíme je. Opakujeme to tak dlouho, dokud není vše seřazeno.

Obrázek 9.1: Bubble Sort jako bublinky ve vodě. Větší prvky "probublávají" na konec seznamu.

% Hlavní pravidlo: Seznam je seřazený, pokud...
bubblesort(Seznam, Serazeny) :-
    swap(Seznam, NovySeznam), !, % ...se nám podařilo něco prohodit (swap).
    bubblesort(NovySeznam, Serazeny). % Pak zkusíme třídit dál ten nový seznam.

bubblesort(Serazeny, Serazeny). % Pokud už nejde nic prohodit, je hotovo. Seznam je seřazený.

% Pravidlo pro prohození (Swap)
swap([A, B | Zbytek], [B, A | Zbytek]) :-
    A > B. % Prohodíme, pokud A je větší než B (jsou ve špatném pořadí).

swap([Z | Zbytek], [Z | NovyZbytek]) :-
    swap(Zbytek, NovyZbytek). % Jinak zkusíme prohodit něco dál v seznamu (v Ocasu).

Co dělá ten vykřičník !? To je tzv. řez (cut). Říká Prologu: "Pokud jsi úspěšně něco prohodil, už se nevracej zpátky a nezkoušej to jinak. Pokračuj v třídění nového seznamu." Bez něj by byl program strašně pomalý a zkoušel by zbytečné kombinace.

Řešené příklady: Hrajeme si se slovy

Příklad 9.1: Anagramy
Chcete najít všechny přesmyčky slova "ABC"? Použijeme permutation.

?- permutation([a,b,c], X).
X = [a, b, c] ;
X = [a, c, b] ;
X = [b, a, c] ;
X = [b, c, a] ;
X = [c, a, b] ;
X = [c, b, a].

Prolog automaticky vygeneroval všechny možné kombinace. To se hodí třeba pro luštění křížovek nebo šifrování.