Here's an example of saving previous values for calculating prime numbers.
primes = [2, 3]
def prime(i):
"""Return i'th prime number"""
def notPrime(value):
"""Return True if value is not prime"""
sqrt = value**0.5
for p in primes:
if value % p == 0:
return True
if p > sqrt:
return False
# Calculate new prime numbers to fill primes to requested size"""
count = 0
while len(primes) <= i:
value = primes[-1] + 2
while notPrime(value):
value += 2
count += 1
primes.append(value)
if count > 0:
print(f'Calculated {count} new primes')
return primes[i]
print(prime(1))
print(prime(5))
print(prime(7))
print(prime(10))
print(prime(6))
print(primes)
Output:
3
Calculated 4 new primes
13
Calculated 2 new primes
19
Calculated 3 new primes
31
17
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
For this example a list works because the index is adequate for looking up the previously calculated value. You could also use something like this to get numbers from the Fibonacci sequence.
fibonacci = [1, 1]
def fib(i):
"""Return i'th Fibonacci number"""
count = 0
while len(fibonacci) <= i:
fibonacci.append(fibonacci[-1] + fibonacci[-2])
count += 1
if count > 0:
print(f'Calculated {count} new values')
return fibonacci[i]
print(fib(1))
print(fib(5))
print(fib(7))
print(fib(10))
print(fib(6))
print(fibonacci)
Output:
1
Calculated 4 new values
8
Calculated 2 new values
21
Calculated 3 new values
89
13
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
Your problem is a bit trickier. An index will not work as a "key" to retrieve previously calculated values. You will probably use a dictionary. With a dictionary you'll need a key.
results = {}
def addum(x):
key = str(set(x))
result = results.get(key)
if result:
print(f'Reuse {x[0]}, {x[1]}')
else:
result = sum(x)
results[key] = result
return result
numbers = [4, 6, 1, 2, 7, 4, 2, 6, 4, 6, 2, 1]
print([addum(x) for x in zip(numbers[:-1], numbers[1:])])
Output:
Reuse 6, 4
Reuse 4, 6
Reuse 6, 2
Reuse 2, 1
[10, 7, 3, 9, 11, 6, 8, 10, 10, 8, 3]
Doing something like this you have to weigh the effort of calculating the value against the effort of generating keys and managing the dictionary.
This is a more substantial problem that reuses previous results many times.
import random
## Save partial solutions to speed things up.
solutions = {}
def sticks(bag, count):
'''Split bag into count groups. Find the grouping that results
in the highest minimum group score. Group score is the sum of
numbers in the group.
'''
## Reuse partial solution when possible
if score := solutions.get((len(bag), count)):
return score
if count == 1:
score = (sum(bag), [bag])
solutions[(len(bag), count)] = score
return score
best_score = 0
for i in range(1, len(bag)-count+1):
if count > 1:
score, groups = sticks(bag[i:], count-1)
groups = [bag[:i]] + groups
score = min(score, sum(bag[:i]))
if score > best_score:
best_score = score
best = groups
# Comment out following line to see how much time it saves
solutions[(len(bag), count)] = (best_score, best)
return (best_score, best)
bag = list(range(1, 51))
random.shuffle(bag)
print(sticks(bag, 7))