Spaces:
Sleeping
Sleeping
| from functools import wraps | |
| def recurrence_memo(initial): | |
| """ | |
| Memo decorator for sequences defined by recurrence | |
| Examples | |
| ======== | |
| >>> from sympy.utilities.memoization import recurrence_memo | |
| >>> @recurrence_memo([1]) # 0! = 1 | |
| ... def factorial(n, prev): | |
| ... return n * prev[-1] | |
| >>> factorial(4) | |
| 24 | |
| >>> factorial(3) # use cache values | |
| 6 | |
| >>> factorial.cache_length() # cache length can be obtained | |
| 5 | |
| >>> factorial.fetch_item(slice(2, 4)) | |
| [2, 6] | |
| """ | |
| cache = initial | |
| def decorator(f): | |
| def g(n): | |
| L = len(cache) | |
| if n < L: | |
| return cache[n] | |
| for i in range(L, n + 1): | |
| cache.append(f(i, cache)) | |
| return cache[-1] | |
| g.cache_length = lambda: len(cache) | |
| g.fetch_item = lambda x: cache[x] | |
| 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): | |
| 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 | |