Saturday, November 8, 2008

99 problems - python - 26

Generate the combinations of K distinct objects chosen from the N elements of a list In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.

def combinations(lst, size):
if len(lst) < size:
elif size == 0:
yield []
# keep first
for combo in combinations(lst[1:], size-1):
yield [lst[0]] + combo
# skip first
for combo in combinations(lst[1:], size):
yield combo

After I wrote this I remembered that python's test/ also had an implementation of this:

>>> def gcomb(x, k):
... "Generate all combinations of k elements from list x."
... if k > len(x):
... return
... if k == 0:
... yield []
... else:
... first, rest = x[0], x[1:]
... # A combination does or doesn't contain first.
... # If it does, the remainder is a k-1 comb of rest.
... for c in gcomb(rest, k-1):
... c.insert(0, first)
... yield c
... # If it doesn't contain first, it's a k comb of rest.
... for c in gcomb(rest, k):
... yield c

Which is amazingly similar. I guess in python there really is OBWTDI (one best way to do it).

So anyway I think from here on out the questions will continue to be less and less "trivial".

No comments: