simple recursion help

[Michael J. Fromberger]

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