A subword of a word is a word obtained by deleting the letters at some
(non necessarily adjacent) positions in
. It is not to be confused with the
notion of factor where one keeps adjacent positions in
. Sometimes it is
useful to allow repeated uses of the same letter of
in a “generalized”
subword. We call this a subword with repetitions.
For example:
A word can be given either as a string, as a list or as a tuple.
As repetition can occur in the initial word, the subwords of a given words is not a set in general but an enumerated multiset!
Todo
AUTHORS:
Return the set of subwords of w.
INPUT:
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']]
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]
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']]
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)]
Bases: sage.structure.parent.Parent
Subwords of a given word.
EXAMPLES:
sage: Subwords([1,2,3]).cardinality()
8
EXAMPLES:
sage: Subwords([1,2,3]).first()
[]
sage: Subwords((1,2,3)).first()
()
sage: Subwords('123').first()
''
EXAMPLES:
sage: Subwords([1,2,3]).last()
[1, 2, 3]
sage: Subwords((1,2,3)).last()
(1, 2, 3)
sage: Subwords('123').last()
'123'
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 xrange(100):
....: w = S1.random_element()
....: if w in S2:
....: assert(w == [])
sage: for i in xrange(100):
....: w = S2.random_element()
....: if w in S1:
....: assert(w == [])
Bases: sage.combinat.subword.Subwords_w
Subwords with fixed length of a given word.
Returns the number of subwords of w of length k.
EXAMPLES:
sage: Subwords([1,2,3], 2).cardinality()
3
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()
''
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()
''
TESTS:
sage: Subwords('123', 0).last() # trac 10534
''
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 xrange(100):
....: w = S1.random_element()
....: if w in S2:
....: assert(w == [])
sage: for i in xrange(100):
....: w = S2.random_element()
....: if w in S1:
....: assert(w == [])
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
TEST:
We check for trac ticket #5534:
sage: w = ["a", "b", "c", "d"]; ww = ["b", "d"]
sage: x = sage.combinat.subword.smallest_positions(w, ww); ww
['b', 'd']