simple recursion help

Michael J. Fromberger Michael.J.Fromberger at Clothing.Dartmouth.EDU
Sat Oct 23 23:49:47 CEST 2004

```In article <mailman.5375.1098565018.5135.python-list at python.org>,
Steven Bethard <steven.bethard at gmail.com> wrote:

> drs <drs <at> remove-to-send-mail-ecpsoftware.com> writes:
> >
> > I am looking for a list of all unique strings of length x whose
> > elements are from the set a, b, and c.
>
> Does anyone know what this operation is called?  It's not
> permutations or combinations as I understand them since permutations
> and combinations do not allow repetition.  I assume there was already
> a solution for this somewhere, but I didn't know what term to google
> for.

The task you're describing is generation of all strings over a given
alphabet.  Fortunately, there is a fairly simple technique for doing
this -- here is a Python generator to do it:

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]

Cheers,
-M

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

```