## 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:        return    elif size == 0:        yield []    else:        # 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/test_generators.py 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".