gen-k1.py

#!/usr/bin/python3
# Generování všech posloupností 0 a 1 délky n, ve kterých je právě k jedniček
# Posloupnosti vypisujeme v lexikografickém pořadí

### Rekurzivní řešení: generujeme všechny posloupnosti délky s prefixem p,
### do kterých potřebujeme přidat n cifer, z nichž k jsou jedničky.

def genk1(n, k, p=[]):
    if n == 0:
        print("".join(map(str, p)))
    else:
        # 0 můžeme přidat, pokud zbude dost pozic na to, aby se do nich
        # vešly všechny zbývající 1.
        if k < n:
            genk1(n-1, k, p + [0])

        # 1 můžeme přidat, pokud jsme ještě všechny nespotřebovali.
        if k > 0:
            genk1(n-1, k-1, p + [1])

### A opět můžeme podobným způsobem počítat, kolik takových posloupností existuje:

def countk1(n, k):
    if n == 0:
        return 1
    else:
        result = 0
        if k < n:
            result += countk1(n-1, k)
        if k > 0:
            result += countk1(n-1, k-1)
        return result

### Počítací funkce je ovšem pomalá: výsledek je kombinační číslo (poznáváte
### v naší funkci součtový vzorec z Pascalova trojúhelníku?) a nasčítáme ho
### postupně z jedniček. Přitom "n nad n/2" je řádově 2^n / √n. Stejně jako
### u příkladu s Fibonacciho čísly si můžeme mezivýsledky pamatovat a tím
### výpočet zrychlit na O(n^2). Mimochodem, uměli byste to rychleji, aniž
### byste potřebovali mezivýsledky řádově větší než výsledek?

mem = {}        # Slovník, kde klíče jsou tuply (n,k)

def countk1b(n, k):
    if (n,k) not in mem:
        if n == 0:
            result = 1
        else:
            result = 0
            if k < n:
                result += countk1b(n-1, k)
            if k > 0:
                result += countk1b(n-1, k-1)
        mem[(n,k)] = result
    return mem[(n,k)]