#!/usr/bin/python3 # Generování všech posloupností 0 a 1 délky n # Posloupnosti vypisujeme v lexikografickém pořadí ### První řešení: rekurzivní funkce, která vygeneruje všechny posloupnosti ### začínající zadaným prefixem. Parametr "p" je prefix, "n" říká, kolik ještě ### potřebujeme přidat prvků. def gen01(n, p=[]): if n == 0: print("".join(map(str, p))) else: gen01(n-1, p + [0]) gen01(n-1, p + [1]) ### V předchozím řešení se v každém volání funkce kopíruje seznam až n prvků, ### takže i vnitřní vrcholy stromu rekurze mají lineární složitost. Toho se můžeme ### zbavit, když prefix místo v argumentu funkce předáváme v proměnné sdílené ### všemi instancemi funkce. def gen01b(n): def g(n): if n == 0: print("".join(map(str, p))) else: for i in [0, 1]: p.append(i) g(n-1) p.pop() p = [] g(n) ### Funkci gen01 můžeme také upravit, aby místo vygenerování všech posloupností ### jenom spočítala, kolik jich je. Na prefixu nezáleží, tak ho nemusíme předávat. ### Díky tomu stačí jen jedno rekurzivní volání a výsledek znásobit dvěma, ### takže funkce má celkově složitost O(n). def count01(n): if n == 0: return 1 else: return 2 * count01(n-1)