| 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 |
- from functools import wraps
- def recurrence_memo(initial):
- """
- Memo decorator for sequences defined by recurrence
- See usage examples e.g. in the specfun/combinatorial module
- """
- cache = initial
- def decorator(f):
- @wraps(f)
- def g(n):
- L = len(cache)
- if n <= L - 1:
- return cache[n]
- for i in range(L, n + 1):
- cache.append(f(i, cache))
- return cache[-1]
- return g
- return decorator
- def assoc_recurrence_memo(base_seq):
- """
- Memo decorator for associated sequences defined by recurrence starting from base
- base_seq(n) -- callable to get base sequence elements
- XXX works only for Pn0 = base_seq(0) cases
- XXX works only for m <= n cases
- """
- cache = []
- def decorator(f):
- @wraps(f)
- def g(n, m):
- L = len(cache)
- if n < L:
- return cache[n][m]
- for i in range(L, n + 1):
- # get base sequence
- F_i0 = base_seq(i)
- F_i_cache = [F_i0]
- cache.append(F_i_cache)
- # XXX only works for m <= n cases
- # generate assoc sequence
- for j in range(1, i + 1):
- F_ij = f(i, j, cache)
- F_i_cache.append(F_ij)
- return cache[n][m]
- return g
- return decorator
|
