9. úkol - Permutations

Cílem devátého úkolu je vygeneroval list všech 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 rekurzi a 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?

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:

import itertools

def permutations(array):
  return list(itertools.permutations(array))

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

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ů.

K implementaci můžete použít tuto šablonu: permutations.py

Příklady použití

Prázdný list:

print(permutations([]))

vypíše do konzole:

[[]]

Jednoprvkový vstup:

print(permutations([1]))

vypíše do konzole:

[[1]]

Čtyřprvkový vstup:

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']]

Odevzdání

K vyhodnocení používáme python verze 3.

Bodování

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

courses/b6b36zal/zadani/9_permutations.txt · Last modified: 2019/11/18 21:03 by seredlad