Subwords

A subword of a word \(w\) is a word obtained by deleting the letters at some (non necessarily adjacent) positions in \(w\). It is not to be confused with the notion of factor where one keeps adjacent positions in \(w\). Sometimes it is useful to allow repeated uses of the same letter of \(w\) in a “generalized” subword. We call this a subword with repetitions.

For example:

  • “bnjr” is a subword of the word “bonjour” but not a factor;

  • “njo” is both a factor and a subword of the word “bonjour”;

  • “nr” is a subword of “bonjour”;

  • “rn” is not a subword of “bonjour”;

  • “nnu” is not a subword of “bonjour”;

  • “nnu” is a subword with repetitions of “bonjour”;

A word can be given either as a string, as a list or as a tuple.

As repetition can occur in the initial word, in general subwords of a given word form an enumerated multiset rather than a set!

Todo

  • implement subwords with repetitions

  • implement the category of EnumeratedMultiset and inheritate from it when needed (i.e. the initial word has repeated letters)

AUTHORS:

  • Mike Hansen: initial version

  • Florent Hivert (2009/02/06): doc improvements + new methods + bug fixes

sage.combinat.subword.Subwords(w, k=None, element_constructor=None)[source]

Return the set of subwords of w.

INPUT:

  • w – a word (can be a list, a string, a tuple or a word)

  • k – an optional integer to specify the length of subwords

  • element_constructor – an optional function that will be used to build the subwords

EXAMPLES:

sage: S = Subwords(['a','b','c']); S
Subwords of ['a', 'b', 'c']
sage: S.first()
[]
sage: S.last()
['a', 'b', 'c']
sage: S.list()
[[], ['a'], ['b'], ['c'], ['a', 'b'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]

>>> from sage.all import *
>>> S = Subwords(['a','b','c']); S
Subwords of ['a', 'b', 'c']
>>> S.first()
[]
>>> S.last()
['a', 'b', 'c']
>>> S.list()
[[], ['a'], ['b'], ['c'], ['a', 'b'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]

The same example using string, tuple or a word:

sage: S = Subwords('abc'); S
Subwords of 'abc'
sage: S.list()
['', 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc']

sage: S = Subwords((1,2,3)); S
Subwords of (1, 2, 3)
sage: S.list()
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

sage: w = Word([1,2,3])
sage: S = Subwords(w); S
Subwords of word: 123
sage: S.list()
[word: , word: 1, word: 2, word: 3, word: 12, word: 13, word: 23, word: 123]

>>> from sage.all import *
>>> S = Subwords('abc'); S
Subwords of 'abc'
>>> S.list()
['', 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc']

>>> S = Subwords((Integer(1),Integer(2),Integer(3))); S
Subwords of (1, 2, 3)
>>> S.list()
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

>>> w = Word([Integer(1),Integer(2),Integer(3)])
>>> S = Subwords(w); S
Subwords of word: 123
>>> S.list()
[word: , word: 1, word: 2, word: 3, word: 12, word: 13, word: 23, word: 123]

Using word with specified length:

sage: S = Subwords(['a','b','c'], 2); S
Subwords of ['a', 'b', 'c'] of length 2
sage: S.list()
[['a', 'b'], ['a', 'c'], ['b', 'c']]

>>> from sage.all import *
>>> S = Subwords(['a','b','c'], Integer(2)); S
Subwords of ['a', 'b', 'c'] of length 2
>>> S.list()
[['a', 'b'], ['a', 'c'], ['b', 'c']]

An example that uses the element_constructor argument:

sage: p = Permutation([3,2,1])
sage: Subwords(p, element_constructor=tuple).list()
[(), (3,), (2,), (1,), (3, 2), (3, 1), (2, 1), (3, 2, 1)]
sage: Subwords(p, 2, element_constructor=tuple).list()
[(3, 2), (3, 1), (2, 1)]

>>> from sage.all import *
>>> p = Permutation([Integer(3),Integer(2),Integer(1)])
>>> Subwords(p, element_constructor=tuple).list()
[(), (3,), (2,), (1,), (3, 2), (3, 1), (2, 1), (3, 2, 1)]
>>> Subwords(p, Integer(2), element_constructor=tuple).list()
[(3, 2), (3, 1), (2, 1)]
class sage.combinat.subword.Subwords_w(w, element_constructor)[source]

Bases: Parent

Subwords of a given word.

cardinality()[source]

EXAMPLES:

sage: Subwords([1,2,3]).cardinality()
8

>>> from sage.all import *
>>> Subwords([Integer(1),Integer(2),Integer(3)]).cardinality()
8
first()[source]

EXAMPLES:

sage: Subwords([1,2,3]).first()
[]
sage: Subwords((1,2,3)).first()
()
sage: Subwords('123').first()
''

>>> from sage.all import *
>>> Subwords([Integer(1),Integer(2),Integer(3)]).first()
[]
>>> Subwords((Integer(1),Integer(2),Integer(3))).first()
()
>>> Subwords('123').first()
''
last()[source]

EXAMPLES:

sage: Subwords([1,2,3]).last()
[1, 2, 3]
sage: Subwords((1,2,3)).last()
(1, 2, 3)
sage: Subwords('123').last()
'123'

>>> from sage.all import *
>>> Subwords([Integer(1),Integer(2),Integer(3)]).last()
[1, 2, 3]
>>> Subwords((Integer(1),Integer(2),Integer(3))).last()
(1, 2, 3)
>>> Subwords('123').last()
'123'
random_element()[source]

Return a random subword with uniform law.

EXAMPLES:

sage: S1 = Subwords([1,2,3,2,1,3])
sage: S2 = Subwords([4,6,6,6,7,4,5,5])
sage: for i in range(100):
....:   w = S1.random_element()
....:   if w in S2:
....:       assert not w
sage: for i in range(100):
....:   w = S2.random_element()
....:   if w in S1:
....:       assert not w

>>> from sage.all import *
>>> S1 = Subwords([Integer(1),Integer(2),Integer(3),Integer(2),Integer(1),Integer(3)])
>>> S2 = Subwords([Integer(4),Integer(6),Integer(6),Integer(6),Integer(7),Integer(4),Integer(5),Integer(5)])
>>> for i in range(Integer(100)):
...   w = S1.random_element()
...   if w in S2:
...       assert not w
>>> for i in range(Integer(100)):
...   w = S2.random_element()
...   if w in S1:
...       assert not w
class sage.combinat.subword.Subwords_wk(w, k, element_constructor)[source]

Bases: Subwords_w

Subwords with fixed length of a given word.

cardinality()[source]

Return the number of subwords of w of length k.

EXAMPLES:

sage: Subwords([1,2,3], 2).cardinality()
3

>>> from sage.all import *
>>> Subwords([Integer(1),Integer(2),Integer(3)], Integer(2)).cardinality()
3
first()[source]

EXAMPLES:

sage: Subwords([1,2,3],2).first()
[1, 2]
sage: Subwords([1,2,3],0).first()
[]
sage: Subwords((1,2,3),2).first()
(1, 2)
sage: Subwords((1,2,3),0).first()
()
sage: Subwords('123',2).first()
'12'
sage: Subwords('123',0).first()
''

>>> from sage.all import *
>>> Subwords([Integer(1),Integer(2),Integer(3)],Integer(2)).first()
[1, 2]
>>> Subwords([Integer(1),Integer(2),Integer(3)],Integer(0)).first()
[]
>>> Subwords((Integer(1),Integer(2),Integer(3)),Integer(2)).first()
(1, 2)
>>> Subwords((Integer(1),Integer(2),Integer(3)),Integer(0)).first()
()
>>> Subwords('123',Integer(2)).first()
'12'
>>> Subwords('123',Integer(0)).first()
''
last()[source]

EXAMPLES:

sage: Subwords([1,2,3],2).last()
[2, 3]
sage: Subwords([1,2,3],0).last()
[]
sage: Subwords((1,2,3),2).last()
(2, 3)
sage: Subwords((1,2,3),0).last()
()
sage: Subwords('123',2).last()
'23'
sage: Subwords('123',0).last()
''

>>> from sage.all import *
>>> Subwords([Integer(1),Integer(2),Integer(3)],Integer(2)).last()
[2, 3]
>>> Subwords([Integer(1),Integer(2),Integer(3)],Integer(0)).last()
[]
>>> Subwords((Integer(1),Integer(2),Integer(3)),Integer(2)).last()
(2, 3)
>>> Subwords((Integer(1),Integer(2),Integer(3)),Integer(0)).last()
()
>>> Subwords('123',Integer(2)).last()
'23'
>>> Subwords('123',Integer(0)).last()
''
random_element()[source]

Return a random subword of given length with uniform law.

EXAMPLES:

sage: S1 = Subwords([1,2,3,2,1],3)
sage: S2 = Subwords([4,4,5,5,4,5,4,4],3)
sage: for i in range(100):
....:   w = S1.random_element()
....:   if w in S2:
....:       assert not w
sage: for i in range(100):
....:   w = S2.random_element()
....:   if w in S1:
....:       assert not w

>>> from sage.all import *
>>> S1 = Subwords([Integer(1),Integer(2),Integer(3),Integer(2),Integer(1)],Integer(3))
>>> S2 = Subwords([Integer(4),Integer(4),Integer(5),Integer(5),Integer(4),Integer(5),Integer(4),Integer(4)],Integer(3))
>>> for i in range(Integer(100)):
...   w = S1.random_element()
...   if w in S2:
...       assert not w
>>> for i in range(Integer(100)):
...   w = S2.random_element()
...   if w in S1:
...       assert not w
sage.combinat.subword.smallest_positions(word, subword, pos=0)[source]

Return the smallest positions for which subword appears as a subword of word.

If pos is specified, then it returns the positions of the first appearance of subword starting at pos.

If subword is not found in word, then return False.

EXAMPLES:

sage: sage.combinat.subword.smallest_positions([1,2,3,4], [2,4])
[1, 3]
sage: sage.combinat.subword.smallest_positions([1,2,3,4,4], [2,4])
[1, 3]
sage: sage.combinat.subword.smallest_positions([1,2,3,3,4,4], [3,4])
[2, 4]
sage: sage.combinat.subword.smallest_positions([1,2,3,3,4,4], [3,4],2)
[2, 4]
sage: sage.combinat.subword.smallest_positions([1,2,3,3,4,4], [3,4],3)
[3, 4]
sage: sage.combinat.subword.smallest_positions([1,2,3,4], [2,3])
[1, 2]
sage: sage.combinat.subword.smallest_positions([1,2,3,4], [5,5])
False
sage: sage.combinat.subword.smallest_positions([1,3,3,4,5],[3,5])
[1, 4]
sage: sage.combinat.subword.smallest_positions([1,3,3,5,4,5,3,5],[3,5,3])
[1, 3, 6]
sage: sage.combinat.subword.smallest_positions([1,3,3,5,4,5,3,5],[3,5,3],2)
[2, 3, 6]
sage: sage.combinat.subword.smallest_positions([1,2,3,4,3,4,4],[2,3,3,1])
False
sage: sage.combinat.subword.smallest_positions([1,3,3,5,4,5,3,5],[3,5,3],3)
False

>>> from sage.all import *
>>> sage.combinat.subword.smallest_positions([Integer(1),Integer(2),Integer(3),Integer(4)], [Integer(2),Integer(4)])
[1, 3]
>>> sage.combinat.subword.smallest_positions([Integer(1),Integer(2),Integer(3),Integer(4),Integer(4)], [Integer(2),Integer(4)])
[1, 3]
>>> sage.combinat.subword.smallest_positions([Integer(1),Integer(2),Integer(3),Integer(3),Integer(4),Integer(4)], [Integer(3),Integer(4)])
[2, 4]
>>> sage.combinat.subword.smallest_positions([Integer(1),Integer(2),Integer(3),Integer(3),Integer(4),Integer(4)], [Integer(3),Integer(4)],Integer(2))
[2, 4]
>>> sage.combinat.subword.smallest_positions([Integer(1),Integer(2),Integer(3),Integer(3),Integer(4),Integer(4)], [Integer(3),Integer(4)],Integer(3))
[3, 4]
>>> sage.combinat.subword.smallest_positions([Integer(1),Integer(2),Integer(3),Integer(4)], [Integer(2),Integer(3)])
[1, 2]
>>> sage.combinat.subword.smallest_positions([Integer(1),Integer(2),Integer(3),Integer(4)], [Integer(5),Integer(5)])
False
>>> sage.combinat.subword.smallest_positions([Integer(1),Integer(3),Integer(3),Integer(4),Integer(5)],[Integer(3),Integer(5)])
[1, 4]
>>> sage.combinat.subword.smallest_positions([Integer(1),Integer(3),Integer(3),Integer(5),Integer(4),Integer(5),Integer(3),Integer(5)],[Integer(3),Integer(5),Integer(3)])
[1, 3, 6]
>>> sage.combinat.subword.smallest_positions([Integer(1),Integer(3),Integer(3),Integer(5),Integer(4),Integer(5),Integer(3),Integer(5)],[Integer(3),Integer(5),Integer(3)],Integer(2))
[2, 3, 6]
>>> sage.combinat.subword.smallest_positions([Integer(1),Integer(2),Integer(3),Integer(4),Integer(3),Integer(4),Integer(4)],[Integer(2),Integer(3),Integer(3),Integer(1)])
False
>>> sage.combinat.subword.smallest_positions([Integer(1),Integer(3),Integer(3),Integer(5),Integer(4),Integer(5),Integer(3),Integer(5)],[Integer(3),Integer(5),Integer(3)],Integer(3))
False