simple recursion help
Michael J. Fromberger
Michael.J.Fromberger at Clothing.Dartmouth.EDU
Sun Oct 24 07:58:14 EDT 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