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

No comments:

Ranking and Unranking permutations

I've been a big fan of Skiena's Algorithm Design Manual , I recently found my first edition of the book (although I own the third ed...