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
No comments:
Post a Comment