gen-01.py

#!/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)