Subwords

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:

• “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 or as a list.

AUTHORS:

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

sage.combinat.subword.Subwords(w, k=None)

Returns the combinatorial class of subwords of w. The word w can be given by either a string or a list.

If k is specified, then it returns the combinatorial class of subwords of w of length k.

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

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

class sage.combinat.subword.Subwords_w(w)

Bases: sage.combinat.combinat.CombinatorialClass

cardinality()

EXAMPLES:

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

first()

EXAMPLES:

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

last()

EXAMPLES:

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

class sage.combinat.subword.Subwords_wk(w, k)

Bases: sage.combinat.combinat.CombinatorialClass

cardinality()

Returns the number of subwords of w of length k.

EXAMPLES:

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

first()

EXAMPLES:

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

last()

EXAMPLES:

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

sage.combinat.subword.smallest_positions(word, subword, pos=0)

Returns 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 it returns 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:

sage: w = ["a", "b", "c", "d"]; ww = ["b", "d"]
sage: x = sage.combinat.subword.smallest_positions(w, ww); ww # Trac #5534
['b', 'd']