Space-exhausting solutions using weak compositions with n=k=N without leading zero

self_describing_numbers.py

#!/usr/bin/env python3
from collections import defaultdict
from sys import argv

MAX_MEMOIZATION_LENGTH = 14

def memoized(f):
    cache = {}
    def ret(*args):
        if args[1] > MAX_MEMOIZATION_LENGTH:
            return f(*args)
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return ret

@memoized
def weak_compositions_without_leading_zero(n, k, parent=True):
    if n < 0 or k <= 0:
        return []
    if k == 1:
        return [[n]]
    else:
        ret = []
        for i in range(1 if parent else 0, n + 1):
            for composition in weak_compositions_without_leading_zero(n - i, k - 1, False):
                ret.append([i] + composition)
        return ret

def check_self_describing(n):
    counter = defaultdict(int)
    for d in n:
        counter[d] += 1
    for i in range(len(n)):
        if n[i] != counter[i]:
            return
    return True

for n_of_digits in range(100):
    for res in filter(check_self_describing, weak_compositions_without_leading_zero(n_of_digits, n_of_digits)):
        print("Length {}: {}".format(n_of_digits, res))