Words avoiding patterns

63 ●3 ●11

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.

add a comment

2 Answers

Sort by » oldest newest most voted

answered 6 years ago

rburing

10964 ●4 ●80 ●219 https://www.rburing.nl/

updated 6 years ago

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.

link

Comments

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']]

Polonius ( 6 years ago )

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]

rburing ( 6 years ago )

Indeed. Many thanks.

Polonius ( 6 years ago )

add a comment

answered 6 years ago

Sébastien
3321 ●8 ●44 ●91 http://www.slabbe.org/

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

link

Comments

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.

Polonius ( 6 years ago )

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Words avoiding patterns

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Words avoiding patterns savecancel

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Words avoiding patterns