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".

## No comments:

Post a Comment