Ask Your Question

Why is the Subwords class separated from FiniteWord?

asked 2018-07-11 04:40:01 +0200

evandomme gravatar image

Subwords could be a method of FiniteWord as factors is already one. Is there a reason why this is not the case?

edit retag flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted

answered 2018-07-11 09:49:07 +0200

Sébastien gravatar image

The module was created in 2007 during the translation by Mike Hansen of 30k lines of code from Mupad-Combinat to sage. Around the same time, in 2008, the module sage/combinat/words was created and nothing has ever been done to merge the two.

Notice that the code in is based on itertools.combinations and no wiser algorithm is coded to enumerate distinct subwords.

sage: s = Subwords('aaaaa', 3)
sage: s.__iter__??
       iterator = itertools.combinations(self._w, self._k)
sage: list(s)
['aaa', 'aaa', 'aaa', 'aaa', 'aaa', 'aaa', 'aaa', 'aaa', 'aaa', 'aaa']

If you know the existence of a better algorithm, you are welcome to add it to the file which contains already 3 methods related to subwords:

sage: w = Word('abc')
sage: w.*subword*?
edit flag offensive delete link more

answered 2018-07-11 18:16:24 +0200

vdelecroix gravatar image

updated 2018-07-11 18:17:54 +0200

Here is a function that compute the set of subwords (no repetition)

def subwords(w, W=None):
    Return the subwords of ``w`` without repetition.


    - ``w`` - a finite word (or string or list)

    - ``W`` - an optional parent


        sage: subwords('aab')
        ['', 'a', 'aa', 'b', 'ab', 'aab']
        sage: subwords('aba')
        ['', 'a', 'b', 'ab', 'ba', 'aa', 'aba']
        sage: subwords('aaa')
        ['', 'a', 'aa', 'aaa']

        sage: subwords(Word('abc'))
        [word: , word: a, word: b, word: ab, word: c, word: bc, word: ac, word: abc]
    if W is None:
            W = w.parent()
        except AttributeError:
            W = type(w)

    T = {}
    L = [W()]
    for a in w:
        todo = [(W(),T)] 
        while todo:
            cw, t = todo.pop()
            todo.extend((cw+W(b),tt) for b,tt in t.items())
            if a not in t:
                t[a] = {}
                L.append(cw + W(a))

    return L
edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools


Asked: 2018-07-11 04:40:01 +0200

Seen: 235 times

Last updated: Jul 11 '18