| 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576 |
- 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):
- @wraps(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):
- @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
|
