Words avoiding patterns I'm trying to write variations on the "words" generator from http://doc.sagemath.org/html/en/refer.... 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.

edit retag close merge delete

Sort by » oldest newest most voted 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.

more

Thanks. Calling words inside of non_rep_words was a mistake. But fixing that still doesn't produce the expected output. Rather, I get this:

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


That is because you didn't fix the case l == 1, which I did in my answer. To be explicit:

yield alphabet


is not the same as

for a in alphabet:
yield [a]


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: [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')]

more

Thanks. This module looks very useful. I was searching for this kind of thing under "Combinatorics". There some kind of cross-reference in the documentation.