Revision history [back]

I'm trying to write variations on the "words" generator from http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/tutorial.html. The code there is

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

which produces words in "alphabet" of length l. (Parenthetical remark: Where I've written "for a in alphabet", the original has "for l in alphabet", which looks confusing given that l is also the name of the input length.)

I'd like to modify this generator in various ways, for example to produce words in which the same "letter" does not appear twice in a row. What I've tried is the following:

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

The idea is to take a word w of length l-1 and for each element a of the alphabet, test if it agrees with the end of w, and if it doesn't, then tack it on to w.

This seems to work for l=0,1,2, but fails at l=3. Here's what my terminal looks like:

sage: list(non_rep_words(['a','b'],2))

[['a', 'b'], ['b', 'a']]

sage: list(non_rep_words(['a','b'],3))

[['a', 'a', 'b'], ['a', 'b', 'a'], ['b', 'a', 'b'], ['b', 'b', 'a']]

Clearly I am misunderstanding something basic, and I would appreciate any advice.

Eventually, I'd like to do other kinds of pattern avoidance. For example, elements of my "alphabet" might come in pairs, a yin and a yang version, and I might want to make words in which a_yin does not follow a_yang, and conversely.

I'm trying to write variations on the "words" generator from http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/tutorial.html. The code there is

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

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