I have function in python and would like to use dynamic-programming to increase its speed.
from numpy import array
from collections import Counter
import itertools
import multiprocessing
from sage.parallel.multiprocessing_sage import Pool
def candidates(content, k):
m=sum(content.values())/k
if len(content) < k:
return
for I in itertools.combinations(content, k):
# We ensure that elements inside a k-tuple are sorted
T = (tuple(sorted(I)), )
if m == 1:
yield T
else:
for L in candidates(content - Counter(I), k):
yield T + L
# test
k=3
r1=Counter({1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1}) # sum(r1.values()) is divisable by k
%time list(candidates(r1, k))
# test
k=4
r1=Counter({1:1, 2:1, 3:2, 4:3, 5:1, 6:2, 7:2, 8:2, 9:2}) # sum(r1.values()) is divisable by k
%time list(candidates(r1, k))
Do you have some suggestions? Thank you very much.