From b2bc6a93df64f4a0d3aef5514bf68fa1dd8d8724 Mon Sep 17 00:00:00 2001 From: Tim Peters Date: Sun, 24 Jun 2001 10:14:27 +0000 Subject: Added a "generate k-combinations of a list" example posted to c.l.py. --- Lib/test/test_generators.py | 50 ++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 49 insertions(+), 1 deletion(-) diff --git a/Lib/test/test_generators.py b/Lib/test/test_generators.py index 8a82407..82ab01c 100644 --- a/Lib/test/test_generators.py +++ b/Lib/test/test_generators.py @@ -281,7 +281,7 @@ Guido's binary tree example. """ -# A few examples from Iterator-List and Python-Dev email. +# Examples from Iterator-List and Python-Dev and c.l.py. email_tests = """ @@ -319,6 +319,54 @@ Traceback (most recent call last): ... File "", line 2, in g ValueError: generator already executing + +Next one was posted to c.l.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]: """ # Fun tests (for sufficiently warped notions of "fun"). -- cgit v0.12