From 68d919e4d60b49d7252bf3a3a53299bbad86fe68 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Sun, 25 Jan 2009 21:31:47 +0000 Subject: Improved itertools recipe for generating powerset(). --- Doc/library/itertools.rst | 8 +++----- Lib/test/test_itertools.py | 12 +++++------- 2 files changed, 8 insertions(+), 12 deletions(-) diff --git a/Doc/library/itertools.rst b/Doc/library/itertools.rst index 903284e..b7cd431 100644 --- a/Doc/library/itertools.rst +++ b/Doc/library/itertools.rst @@ -687,11 +687,9 @@ which incur interpreter overhead. nexts = cycle(islice(nexts, pending)) def powerset(iterable): - "powerset('ab') --> set([]), set(['a']), set(['b']), set(['a', 'b'])" - # Recipe credited to Eric Raymond - pairs = [(2**i, x) for i, x in enumerate(iterable)] - for n in xrange(2**len(pairs)): - yield set(x for m, x in pairs if m&n) + "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" + s = list(iterable) + return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) def combinations_with_replacement(iterable, r): "combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC" diff --git a/Lib/test/test_itertools.py b/Lib/test/test_itertools.py index a62bad2..9b399c0 100644 --- a/Lib/test/test_itertools.py +++ b/Lib/test/test_itertools.py @@ -1287,11 +1287,9 @@ Samuele ... nexts = cycle(islice(nexts, pending)) >>> def powerset(iterable): -... "powerset('ab') --> set([]), set(['a']), set(['b']), set(['a', 'b'])" -... # Recipe credited to Eric Raymond -... pairs = [(2**i, x) for i, x in enumerate(iterable)] -... for n in xrange(2**len(pairs)): -... yield set(x for m, x in pairs if m&n) +... "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" +... s = list(iterable) +... return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) >>> def combinations_with_replacement(iterable, r): ... "combinations_with_replacement('ABC', 3) --> AA AB AC BB BC CC" @@ -1385,8 +1383,8 @@ perform as purported. >>> list(roundrobin('abc', 'd', 'ef')) ['a', 'd', 'e', 'b', 'f', 'c'] ->>> map(sorted, powerset('ab')) -[[], ['a'], ['b'], ['a', 'b']] +>>> list(powerset([1,2,3])) +[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)] >>> list(combinations_with_replacement('abc', 2)) [('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'b'), ('b', 'c'), ('c', 'c')] -- cgit v0.12