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>,
 Steven Bethard <steven.bethard at> wrote:

> drs <drs <at>> 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:

            if sum(ixs) == 0:

        ixs += [0]


Michael J. Fromberger             | Lecturer, Dept. of Computer Science  | Dartmouth College, Hanover, NH, USA

More information about the Python-list mailing list