Getting all possible combinations of list items
Tim Peters
tim.one at home.com
Mon Sep 17 02:23:36 EDT 2001
[Greg Krohn]
> ...
> scratching my head over 'magic' code,
Generators in 2.2 are "the natural" way to do this kind of thing. Here from
test_generators.py:
>>> 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
>>> seq = range(1, 5)
>>> for k in range(len(seq) + 2):
... print "%d-combs of %s:" % (k, seq)
... for c in gcomb(seq, k):
... print " ", c
0-combs of [1, 2, 3, 4]:
[]
1-combs of [1, 2, 3, 4]:
[1]
[2]
[3]
[4]
2-combs of [1, 2, 3, 4]:
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
3-combs of [1, 2, 3, 4]:
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
4-combs of [1, 2, 3, 4]:
[1, 2, 3, 4]
5-combs of [1, 2, 3, 4]:
That was posted to c.l.py before. Go to a search engine and look for it,
and you'll find an equivalent recursive (non-generator) routine too, which
looks *almost* exactly the same.
no-need-for-magic-just-need-care-at-the-boundaries-ly y'rs - tim
More information about the Python-list
mailing list