I've been trying to relearn some of the combinatorics I used to know, I redid a nice recursive algorithm (from early university days), with python it looks so beautiful and nice. A simple implementation is below, so nice and simple.

# # I'm inspired by two algorithms I saw, both are recursive. # # Example: # ((1, 2, 3, 4), 2) - means select 2 out of 3 # should produce (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) # # The idea from a recursive perspective is this # we pick an index - say 1, then we pick the next (n-1) elements # to go with it # def rec_comb(a, i, j, k, n): # # array a built upto index i # selected k at a time of max # length n # if (i == k): print a[0:k] return for l in range(j, n): a[i] = l rec_comb(a, i+1, l+1, k, n) return def combination(n, k): # # n (numbers from 1..n), chosen k at a time # a = [0 for i in range(0, n)] rec_comb(a, 0, 0, k, n)The sample output for ${6 \choose 3}$ is:

[0, 1, 2] [0, 1, 3] [0, 1, 4] [0, 1, 5] [0, 2, 3] [0, 2, 4] [0, 2, 5] [0, 3, 4] [0, 3, 5] [0, 4, 5] [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 3, 4] [1, 3, 5] [1, 4, 5] [2, 3, 4] [2, 3, 5] [2, 4, 5] [3, 4, 5]The output lends itself to a simple and nice iterative algorithm, I'll follow up on.

The interesting follow up to combinatorial generation algorithms is using ranking and unranking. At this point, I think we need a O(n) to identify if two combinations are the same -- given in any order of elements. For example to compare $\{1, 2, 3\}, \{1, 3, 2\}, \{2, 1, 3\}, \{3, 1, 2\}, \{2, 3, 1\}, \{3, 2, 1\}$ we need to identify them and associate the same rank with them. I think for a subset of size $k$, the cost of ranking is $\theta(k)$, but I need to see if there is a better way to do it.

## No comments:

Post a Comment