Ask Your Question
2

Words avoiding patterns

asked 2018-08-04 04:05:49 -0500

Polonius gravatar image

updated 2018-08-04 04:14:13 -0500

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 flag offensive close merge delete

2 answers

Sort by » oldest newest most voted
2

answered 2018-08-04 08:10:58 -0500

updated 2018-08-04 08:19:59 -0500

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.

edit flag offensive delete link more

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 gravatar imagePolonius ( 2018-08-04 08:30:43 -0500 )edit

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 gravatar imagerburing ( 2018-08-04 09:23:28 -0500 )edit

Indeed. Many thanks.

Polonius gravatar imagePolonius ( 2018-08-04 10:42:50 -0500 )edit
2

answered 2018-08-04 08:30:18 -0500

Sébastien gravatar image

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')]
edit flag offensive delete link more

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 gravatar imagePolonius ( 2018-08-04 10:44:37 -0500 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-08-04 04:05:49 -0500

Seen: 62 times

Last updated: Aug 04