simple recursion help

Michael J. Fromberger Michael.J.Fromberger at Clothing.Dartmouth.EDU
Sun Oct 24 13:58:14 CEST 2004


In article <1gm4vyt.1eykww1d7p0i8N%aleaxit at yahoo.com>,
 aleaxit at yahoo.com (Alex Martelli) wrote:

> Michael J. Fromberger <Michael.J.Fromberger at Clothing.Dartmouth.EDU>
> wrote:
> > 
> > def lexgen(alph, maxlen = None):
> >     """Generate all the possible strings over the given alphabet in 
> >     lexicographic order.  Stop after generating the strings of maxlen,
> >     if provided; otherwise, generate forever."""
> >     
> >     ixs = []
> >     
> >     while maxlen is None or len(ixs) <= maxlen:
> >         while True:
> >             yield str.join('', [ alph[ixs[x]] for x in
> >                                  xrange(len(ixs) - 1, -1, -1) ])
> > 
> >             for pos in xrange(len(ixs)):
> >                 ixs[pos] = (ixs[pos] + 1) % len(alph)
> >                 if ixs[pos] <> 0:
> >                     break
> > 
> >             if sum(ixs) == 0:
> >                 break
> > 
> >         ixs += [0]
> 
> Nice, and different from what was offered in the other recent thread
> (and from what the OP asked for) since you generate all strings of
> length up to maxlen, while the request was for just those of length
> exactly x.  Still, this can easily be restricted, and maybe a few
> Pythonic tweaks with it...:

Hi, Alex,

Thanks for the feedback, you make some good points.  

> In 2.4 one can do a bit better for the yield, with
> 
>         yield ''.join(alph[i] for i in reversed(ixs))
> 
> [generator expression vs list comprehension, and reversed built-in vs 
> reversal by slicing].

Yes, I'm aware of both of those improvements, but since I do not yet 
have Python 2.4, I did not use any of its new features in my solution. 

In any case, thank you for the helpful comments on both sides of the 2.4 
divide.

Cheers,
-M

-- 
Michael J. Fromberger             | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/  | Dartmouth College, Hanover, NH, USA



More information about the Python-list mailing list