ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 04 Aug 2018 11:05:49 +0200Words avoiding patternshttps://ask.sagemath.org/question/43249/words-avoiding-patterns/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.PoloniusSat, 04 Aug 2018 11:05:49 +0200https://ask.sagemath.org/question/43249/