Words avoiding patterns

edit

Note the original function words is recursive: it calls itself.

Your new function non_rep_words should also call itself, rather than calling the old words:

def non_rep_words(alphabet,l):
    if l == 0:
        yield []
    elif l == 1:
        for a in alphabet:
            yield [a]
    else:
        for word in non_rep_words(alphabet, l-1):
            for a in alphabet:
                if word[-1] != a:
                    yield word+[a]

Here I also corrected the case l == 1.

Note that you could avoid this case by adding an extra clause to your if statement:

def non_rep_words(alphabet,l):
    if l == 0:
        yield []
    else:
        for word in non_rep_words(alphabet, l-1):
            for a in alphabet:
                if len(word) == 0 or word[-1] != a:
                    yield word+[a]

However this will perform many pointless comparisons to 0, so it is probably slower.

You may use RecursivelyEnumeratedSet in Sage to do these kind of thing:

sage: def non_rep_words(alphabet):
....:     def children(w):
....:         return [w+(a,) for a in alphabet if not w or w[-1] != a]
....:     seeds = [tuple()]
....:     R = RecursivelyEnumeratedSet(seeds, children, structure='forest')
....:     return R
....: 
sage: Rab = non_rep_words(['a','b'])
sage: Rab
An enumerated set with a forest structure
sage: it = Rab.breadth_first_search_iterator()
sage: [next(it) for _ in range(6)]
[(), ('a',), ('b',), ('a', 'b'), ('b', 'a'), ('a', 'b', 'a')]
sage: list(Rab.elements_of_depth_iterator(3))
[('a', 'b', 'a'), ('b', 'a', 'b')]
sage: list(Rab.elements_of_depth_iterator(4))
[('a', 'b', 'a', 'b'), ('b', 'a', 'b', 'a')]
sage: list(Rab.elements_of_depth_iterator(5))
[('a', 'b', 'a', 'b', 'a'), ('b', 'a', 'b', 'a', 'b')]