The function you're looking for, that will make this completely trivial is itertools.combinations
.
>>> from itertools import combinations
>>> len(list(a for a in combinations(range(1, 101), 3)))
161700
I'd suggest an implementation based off of yours as something like this:
def findbest(origarray, denom):
current = origarray
i = 1
while(i < size):
if(i in denom):
current[i] = 1
coinlist[i] = [i]
else:
k = 1
while(k < 1 + (i/2)):
c = current[k] + current[i-k]
if(c < current[i]):
current[i] = c
coinlist[i] = coinlist[k] + coinlist[i-k]
k+=1
#print i, current[i], coinlist[i]
i+=1
return current
size = 100
def reset_cache():
i = 1
global coinlist
coinlist = [[]]
global origarray
origarray = [0]
while(i < size):
origarray.append(100)
coinlist.append([])
i += 1
reset_cache()
denom = [1,5,10,25,50]
x = findbest(origarray, denom)
total=0
for value in findbest(origarray,denom):
total += value
print total
print "\n\n\n"
print x
from itertools import combinations
best = ((0,0,0), 1e6)
for comb in combinations(range(1, 101), 3):
#print "Considering: %s" % comb
reset_cache()
total = 0
for value in findbest(origarray, comb):
total += value
if total < best[1]:
print "%s beat best with %d" % (comb, total)
best = (comb, total)
print best
But I am bothered by needing what I suppose is a coin cache? I'm not sure, I didn't read your code too hard. But I don't like the necessity of passing in a few arrays to make it work. It should be self-contained.
EDIT: Seems to me that you can actually get away
for comb in [(1,) + a for a in combinations(range(2, 101), 2)]:
because any valid change system will need to have a 1 cent coin. This makes the code run much faster because
>>> len([(1,) + a for a in combinations(range(2, 101), 2)])
4851