PEP 255: Simple Generators

[Roman Suzi]

On Sun, 24 Jun 2001, Neil Schemenauer wrote:

>Roman Suzi wrote:
>> This implementation is cool, but how fast will be recursive generators?
>> How large is the overhead to defrost execution frame each time? Will it be
>> faster than functional gcomb?
>
>Why don't you write one and we will compare it to Tim's generator
>version? :-) I'll stick my neck and speculate that resuming a generator
>is measurably faster than calling a function.

Could you try my comb version? I am sure it's faster!
(I used the same algorithms in it. Only implementation differs)

#!/usr/bin/python2.1

def comb(x, k):
    "Generate all combinations of k elements from list x."

    if k > len(x): return []
    if k == 0: return [[]]
    first, rest = x[0:1], x[1:]
    return [first+w for w in comb(rest, k-1)] + comb(rest, k)

# Tim's code below this line unchanged:

seq = range(1, 5)
for k in range(len(seq) + 2):
    print "%d-combs of %s:\n    " % (k, seq),
    for c in comb(seq, k):
        print c, " ",
    print


"""
Which prints:

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]:

"""

Probably, [g]comb could be added to regression tests of generators.

Sincerely yours, Roman Suzi
-- 
_/ Russia _/ Karelia _/ Petrozavodsk _/ rnd at onego.ru _/
_/ Sunday, June 24, 2001 _/ Powered by Linux RedHat 6.2 _/
_/ "Ok, I pulled the pin. Now what? Where are you going?" _/