ASKSAGE: Sage Q&A Forum - Latest question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 04 Aug 2018 04:05:49 -0500Words avoiding patternshttp://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 04:05:49 -0500http://ask.sagemath.org/question/43249/How do I identify the set of words of given length in matrix generatorshttp://ask.sagemath.org/question/32955/how-do-i-identify-the-set-of-words-of-given-length-in-matrix-generators/I should mention that I am a beginner with Sage so please bear with me. Also this question regards a small sub-step of what this question is about:
http://ask.sagemath.org/question/32935/how-to-efficiently-test-whether-a-matrix-can-be-written-as-a-certain-type-of-word/
But I expect the current issue would be much more common.
Take a small set of matrices, let's say 3 of them: m1, m2, m3. Let G be the group generated by these matrices. I want to be able to work with words of a given length in these generators. Let Gn be the words of length n in G. Then for example
G1 = (m1,m2,m3,m1^(-1),m2^(-1),m3^(-1)).
Is there a pre-built module for working with words of length n for n arbitrary? If not, I'm sure someone can find improvements on the approach I am taking. For instance to get G2, I have been doing this:
G2 = []
for g in G1:
for h in G1:
if g*h not in G2:
G2.append(g*h)
if h*g not in G2:
G2.append(h*g)
This gives me everything in G2, and avoids repitition, but does not extend well to Gn.
To get G3 I have been doing this:
G3 = []
for g in G2:
for h in G1:
if g*h not in G2:
if g*h not in G1:
G2.append(g*h)
if h*g not in G2:
if h*g not in G1:
G2.append(h*g)
If I want to go to G4 in this way, I need to add a line that makes sure my new addition isn't in G3, and I need to keep adding new lines at each increase in word length. I would like to define a function which outputs all words of length n, but as you can imagine from my approach above that is not working out well.
j0equ1nnFri, 01 Apr 2016 18:30:25 -0500http://ask.sagemath.org/question/32955/free algebra and indexed lettershttp://ask.sagemath.org/question/8601/free-algebra-and-indexed-letters/I try to work with a Combinatorial Free Module with basis a set of Words over an alphabet of indexed letters (y1,y2,...).
For example, I define
from sage.combinat.free_module import CombinatorialFreeModule as CFM
Mots=Words(['y1','y2','y3','y4','y5','y6','y7','y8'])
Module=CFM(QQ,Mots)
But I have some problems with the letters. For example :
mot=Word('y1')
sage: mot
word: y1
sage: mot in Mots
False
Is there a way to cure this problem ?Matthieu DeneufchâtelFri, 30 Dec 2011 05:41:57 -0600http://ask.sagemath.org/question/8601/