## Thursday, July 06, 2017

### Iterative combinations algorithm

The algorithm is quite straight forward, see the code in python below

#
# Do iterative combinations generation
# From Knuth's observation, we know for (6 3) that
# [0, 1, 2]
# [0, 1, 3]
# ..
# [3, 4, 5]
# Basically we can see a set of for loops, if we call the columns c1,c2 and c3 then
#
# for c3 = 2 to n-1
#  for c2 = 1 to c3-1
#   for c1 = 0 to c2-1
#
# The loop gives us what we need
# My implementation is based on an index (i) and max (n)
# which are used to determine the next value to generate
#
def iterative_combination(n, k):
a = [i for i in range(0, n)]
index = k - 1
done = False
while (done == False):
print a[0:k]
while (a[index] == n - (k - index)): # boundary for that index
index = index - 1
if (index < 0):
done = True
break
a[index] = a[index] + 1
while (index < k - 1):
index = index + 1
if (a[index] == (n - (k - index))): # initialize the next neighbour
a[index] = a[index - 1] + 1



### Dynamic programming for the binomial coefficient

More fun things, this time with some visualisation of what happens when memoisation is used and what happens when we don't. I don'...