====== 9. úkol - Permutations ======

Cílem devátého úkolu je vygeneroval [[https://docs.python.org/3/tutorial/datastructures.html|list]] všech [[https://en.wikipedia.org/wiki/Permutation|permutací]] daných prvků. Tzn. například pro prvky ''[1, 2, 3]'' vrátit ''%%[[%%1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1%%]]%%''.

V řešení využijte především [[https://en.wikipedia.org/wiki/Recursion_(computer_science)|rekurzi]] a [[https://docs.python.org/3/tutorial/datastructures.html|metody pracující s listy]]. Problém si zkuste nejdříve vyřešit na papíře. Najděte si deterministický postup pro generování permutací. Inspirujte se například obrázkem uvedeným níže (barvami se nenechte zmást). Odpovězte si na otázky: Co má funkce vrátit pro jeden prvek? Pro dva prvky? A jak toho využít, když budeme uvažovat prvky tři?

{{ :courses:b6b36zal:zadani:perm.jpg?600 |}}

<note warning>
Při použití externích knihoven bude práce hodnocena jako neodevzdaná (a to i zpětně)!

Tzn. vyhněte se řešení typu:

<code>
import itertools

def permutations(array):
  return list(itertools.permutations(array))
</code>  

Tímto způsobem se nic nového nenaučíte ;-)
</note>


==== Zadání ====
Vytvořte soubor permutations.py a v něm stejnojmennou funkci permutations(array) přijímající list s prvky. Funkce bude vracet list všech možných permutací těchto prvků.

<note tip>K implementaci můžete použít tuto šablonu: {{:courses:b6b36zal:zadani:permutations.py|}}</note>

==== Příklady použití ====
Prázdný list:
<WRAP center round box 60%>
''print(permutations([]))''\\

**vypíše do konzole**:

''%%[[%%]]''
</WRAP>

Jednoprvkový vstup:
<WRAP center round box 60%>
''print(permutations([1]))''\\

**vypíše do konzole**:

''%%[[1%%]]''
</WRAP>

Čtyřprvkový vstup:
<WRAP center round box 60%>
''print(permutations(['a', 'b', 'c', 'd']))''\\

**vypíše do konzole**:

''%%[[%%'a', 'b', 'c', 'd'], ['a', 'b', 'd', 'c'], ['a', 'c', 'b', 'd'], ['a', 'c', 'd', 'b'], ['a', 'd', 'b', 'c'], ['a', 'd', 'c', 'b'], ['b', 'a', 'c', 'd'], ['b', 'a', 'd', 'c'], ['b', 'c', 'a', 'd'], ['b', 'c', 'd', 'a'], ['b', 'd', 'a', 'c'], ['b', 'd', 'c', 'a'], ['c', 'a', 'b', 'd'], ['c', 'a', 'd', 'b'], ['c', 'b', 'a', 'd'], ['c', 'b', 'd', 'a'], ['c', 'd', 'a', 'b'], ['c', 'd', 'b', 'a'], ['d', 'a', 'b', 'c'], ['d', 'a', 'c', 'b'], ['d', 'b', 'a', 'c'], ['d', 'b', 'c', 'a'], ['d', 'c', 'a', 'b'], ['d', 'c', 'b', 'a'%%]]%%
''
</WRAP>

==== Odevzdání ====
<note warning>K vyhodnocení používáme python verze 3.</note>

==== Bodování ====
Za úlohu je možné získat maximálně **5 bodů**.