18.38 Words

Module: sage.combinat.word

Words

Module-level Functions

ShuffleProduct( w1, w2, [shifted=False], [overlapping=False])

Returns the combinatorial class representing the shuffle product between w1 and w2. This consists of all words of length len(w1)+len(w2) which have both w1 and w2 as subwords.

sage: sp = ShuffleProduct([1,2],[3,4]); sp
Shuffle product of [1, 2] and [3, 4]
sage: sp.count()
6
sage: sp.list()
[[1, 2, 3, 4],
 [1, 3, 2, 4],
 [1, 3, 4, 2],
 [3, 1, 2, 4],
 [3, 1, 4, 2],
 [3, 4, 1, 2]]

Words( )

Returns the combinatorial class of words of length k from alphabet.

sage: w = Words([1,2,3], 2); w
Words from [1, 2, 3] of length 2
sage: w.count()
9
sage: w.list()
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]

alphabet_order( alphabet)

Returns the ordering function of the alphabet A. The function takes two elements x and y of A and returns True if x occurs before y in A.

sage: import sage.combinat.word as word
sage: f = word.alphabet_order(['a','b','c'])
sage: f('a', 'b')
True
sage: f('c', 'a')
False
sage: f('b', 'b')
False

charge( word, [check=True])

sage: from sage.combinat.word import charge

sage: charge([1,1,2,2,3])
0
sage: charge([3,1,1,2,2])
1
sage: charge([2,1,1,2,3])
1
sage: charge([2,1,1,3,2])
2
sage: charge([3,2,1,1,2])
2
sage: charge([2,2,1,1,3])
3
sage: charge([3,2,2,1,1])
4

sage: charge([3,3,2,1,1])
Traceback (most recent call last):
...
ValueError: the evaluation of w must be a partition

deg_inv_lex_less( w1, w2)

Returns true if the word w1 is degree inverse lexicographically less than w2. It is restricted to words whose letters can be compared by < as well as summed.

sage: import sage.combinat.word as word
sage: word.deg_inv_lex_less([1,2,4],[1,3,2])
False
sage: word.deg_inv_lex_less([3,2,1],[1,2,3])
True

deg_lex_less( w1, w2)

Returns true if the word w1 is degree lexicographically less than w2. It is restricted to words whose letters can be compared by < as well as summed.

sage: import sage.combinat.word as word
sage: word.deg_lex_less([1,2,3],[1,3,2])
True
sage: word.deg_lex_less([1,2,4],[1,3,2])
False
sage: word.deg_lex_less([3,2,1],[1,2,3])
False

deg_rev_lex_less( w1, w2)

Returns true if the word w1 is degree reverse lexicographically less than w2. It is restricted to words whose letters can be compared by < as well as summed.

sage: import sage.combinat.word as word
sage: word.deg_rev_lex_less([1,2,4],[1,3,2])
False
sage: word.deg_rev_lex_less([3,2,1],[1,2,3])
False

evaluation( w, [alphabet=None])

Returns the evalutation of the word as a list. Either the word must be a word of integers or you must provide the alphabet as a list.

sage: import sage.combinat.word as word
sage: word.evaluation(['b','a','d','b','c','d','b'],['a','b','c','d','e'])
[1, 3, 1, 2, 0]
sage: word.evaluation([1,2,2,1,3])
[2, 2, 1]

evaluation_dict( w)

Returns a dictionary that represents the evalution of the word w.

sage: import sage.combinat.word as word
sage: word.evaluation_dict([2,1,4,2,3,4,2])
{1: 1, 2: 3, 3: 1, 4: 2}
sage: d = word.evaluation_dict(['b','a','d','b','c','d','b'])
sage: map(lambda i: d[i], ['a','b','c','d'])
[1, 3, 1, 2]
sage: word.evaluation_dict([])
{}

evaluation_partition( w)

Returns the evaluation of the word w as a partition.

sage: import sage.combinat.word as word
sage: word.evaluation_partition([2,1,4,2,3,4,2])
[3, 2, 1, 1]

evaluation_sparse( w)

sage: import sage.combinat.word as word
sage: word.evaluation_sparse([4,4,2,5,2,1,4,1])
[[1, 2], [2, 2], [4, 3], [5, 1]]

from_standard_and_evaluation( sp, e, [alphabet=None])

Returns the word given by the standard permutation sp and the evaluation e.

sage: import sage.combinat.word as word
sage: a = [1,2,3,2,2,1,2,1]
sage: e = word.evaluation(a)
sage: sp = word.standard(a)
sage: b = word.from_standard_and_evaluation(sp, e)
sage: b
[1, 2, 3, 2, 2, 1, 2, 1]
sage: a == b
True

inv_lex_less( w1, w2)

Returns true if the word w1 is inverse lexicographically less than w2. It is restricted to words whose letters can be compared by <.

sage: import sage.combinat.word as word
sage: word.inv_lex_less([1,2,4],[1,3,2])
False
sage: word.inv_lex_less([3,2,1],[1,2,3])
True

lex_cmp( w1, w2)

Returns -1 if the word w1 is lexicographically less than w2; otherwise, it returns 1. It is restricted to words whose letters can be compared by <.

Useful to pass into Python's sort()

sage: import sage.combinat.word as word
sage: word.lex_cmp([1,2,3],[1,3,2])
-1
sage: word.lex_cmp([3,2,1],[1,2,3])
1

lex_less( w1, w2)

Returns true if the word w1 is lexicographically less than w2. It is restricted to words whose letters can be compared by <.

sage: import sage.combinat.word as word
sage: word.lex_less([1,2,3],[1,3,2])
True
sage: word.lex_less([3,2,1],[1,2,3])
False

min_lex( l)
Returns the minimal element in lexicographic order of a l of words.

sage: import sage.combinat.word as word
sage: word.min_lex([[1,2,3],[1,3,2],[3,2,1]])
[1, 2, 3]

rev_lex_less( w1, w2)

Returns true if the word w1 is reverse lexicographically less than w2. It is restricted to words whose letters can be compared by <.

sage: import sage.combinat.word as word
sage: word.rev_lex_less([1,2,4],[1,3,2])
True
sage: word.rev_lex_less([3,2,1],[1,2,3])
False

standard( w, [alphabet=None], [ordering=None])

Returns the standard permutation of the word w on the ordered alphabet. It is defined as the permutation with exactly the same number of inversions as w.

By default, the letters are ordered using <. A custom ordering can be specified by passing an ordering function into ordering.

sage: import sage.combinat.word as word
sage: word.standard([1,2,3,2,2,1,2,1])
[1, 4, 8, 5, 6, 2, 7, 3]

swap( w, i, [j=None])

Returns the word w with entries at positions i and j swapped. By default, j = i+1.

sage: import sage.combinat.word as word
sage: word.swap([1,2,3],0,2)
[3, 2, 1]
sage: word.swap([1,2,3],1)
[1, 3, 2]

swap_decrease( w, i)

Returns the word w with positions i and i+1 exchanged if w[i] < w[i+1]. Otherwise, it returns w.

sage: import sage.combinat.word as word
sage: word.swap_decrease([1,3,2],0)
[3, 1, 2]
sage: word.swap_decrease([1,3,2],1)
[1, 3, 2]

swap_increase( w, i)

Returns the word w with positions i and i+1 exchanged if w[i] > w[i+1]. Otherwise, it returns w.

sage: import sage.combinat.word as word
sage: word.swap_increase([1,3,2],0)
[1, 3, 2]
sage: word.swap_increase([1,3,2],1)
[1, 2, 3]

symmetric_group_action_on_values( w, perm)

sage: from sage.combinat.word import symmetric_group_action_on_values
sage: symmetric_group_action_on_values([1,1,1],[1,3,2])
[1, 1, 1]
sage: symmetric_group_action_on_values([1,1,1],[2,1,3])
[2, 2, 2]
sage: symmetric_group_action_on_values([1,2,1],[2,1,3])
[2, 2, 1]
sage: symmetric_group_action_on_values([2,2,2],[2,1,3])
[1, 1, 1]
sage: symmetric_group_action_on_values([2,1,2],[2,1,3])
[2, 1, 1]
sage: symmetric_group_action_on_values([2,2,3,1,1,2,2,3],[1,3,2])
[2, 3, 3, 1, 1, 2, 3, 3]
sage: symmetric_group_action_on_values([2,1,1],[2,1])
[2, 1, 2]
sage: symmetric_group_action_on_values([2,2,1],[2,1])
[1, 2, 1]
sage: symmetric_group_action_on_values([1,2,1],[2,1])
[2, 2, 1]

unmatched_places( w, open, close)

sage: from sage.combinat.word import unmatched_places
sage: unmatched_places([2,2,2,1,1,1],2,1)
([], [])
sage: unmatched_places([1,1,1,2,2,2],2,1)
([0, 1, 2], [3, 4, 5])
sage: unmatched_places([], 2, 1)
([], [])
sage: unmatched_places([1,2,4,6,2,1,5,3],2,1)
([0], [1])
sage: unmatched_places([2,2,1,2,4,6,2,1,5,3], 2, 1)
([], [0, 3])
sage: unmatched_places([3,1,1,1,2,1,2], 2, 1)
([1, 2, 3], [6])

Class: ShuffleProduct_overlapping

class ShuffleProduct_overlapping
ShuffleProduct_overlapping( self, w1, w2)

sage: s = ShuffleProduct([1,2],[3,4],overlapping=True)
sage: s == loads(dumps(s))
True

Functions: iterator

iterator( self)

sage: ShuffleProduct([1,2],[3,4],overlapping=True).list() #indirect doctest
[[1, 2, 3, 4],
 [1, 3, 2, 4],
 [1, 3, 4, 2],
 [3, 1, 2, 4],
 [3, 1, 4, 2],
 [3, 4, 1, 2],
 [4, 2, 4],
 [1, 5, 4],
 [4, 4, 2],
 [1, 3, 6],
 [3, 5, 2],
 [3, 1, 6],
 [4, 6]]

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

sage: ShuffleProduct([1,2],[3,4],overlapping=True).__repr__()
'Overlapping shuffle product of [1, 2] and [3, 4]'

Class: ShuffleProduct_overlapping_r

class ShuffleProduct_overlapping_r
ShuffleProduct_overlapping_r( self, w1, w2, r)

sage: s = ShuffleProduct([1,2],[3,4], overlapping=1)
sage: s == loads(dumps(s))
True

Functions: iterator

iterator( self)

sage: ShuffleProduct([1,2],[3,4], overlapping=1).list() #indirect doctest
[[4, 2, 4], [1, 5, 4], [4, 4, 2], [1, 3, 6], [3, 5, 2], [3, 1, 6]]

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

sage: ShuffleProduct([1,2],[3,4], overlapping=1).__repr__()
'Overlapping shuffle product of [1, 2] and [3, 4] with 1 overlaps'

Class: ShuffleProduct_shifted

class ShuffleProduct_shifted
ShuffleProduct_shifted( self, w1, w2)

sage: s = ShuffleProduct([1,2],[3,4], shifted=True)
sage: s == loads(dumps(s))
True

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

sage: ShuffleProduct([1,2],[3,4], shifted=True).__repr__()
'Shifted shuffle product of [1, 2] and [5, 6]'

Class: ShuffleProduct_w1w2

class ShuffleProduct_w1w2
ShuffleProduct_w1w2( self, w1, w2)

sage: s = ShuffleProduct([1,2],[3,4])
sage: s == loads(dumps(s))
True

Functions: count,$ \,$ iterator

count( self)

Returns the number of words in the shuffle product of w1 and w2.

It is given by binomial(len(w1)+len(w2), len(w1)).

sage: ShuffleProduct([2,3],[3,4]).count()
6

iterator( self)

Returns an iterator for the words in the shuffle product of w1 and w2.

sage: ShuffleProduct([1,2],[3,4]).list() #indirect test
[[1, 2, 3, 4],
 [1, 3, 2, 4],
 [1, 3, 4, 2],
 [3, 1, 2, 4],
 [3, 1, 4, 2],
 [3, 4, 1, 2]]

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__,$ \,$ _proc

__contains__( self, x)

sage: s = ShuffleProduct([1,2],[3,4])
sage: all(i in s for i in s)
True
sage: [2, 1, 3, 4] in s
False

__repr__( self)

sage: repr(ShuffleProduct([1,2],[3,4]))
'Shuffle product of [1, 2] and [3, 4]'

_proc( self, vect)

sage: s = ShuffleProduct([1,2],[3,4])
sage: s._proc([0,1,0,1])
[3, 1, 4, 2]
sage: s._proc([1,1,0,0])
[1, 2, 3, 4]

Class: Words_all

class Words_all

Functions: count,$ \,$ iterator

count( self)

sage: Words().count()
+Infinity

iterator( self)

sage: Words().list() #indirect doctest
Traceback (most recent call last):
...
NotImplementedError

Special Functions: __contains__,$ \,$ __repr__

__contains__( self, x)

sage: 2 in Words()
False
sage: [1,2] in Words()
True

__repr__( self)

sage: Words().__repr__()
'Words'

Class: Words_alphabet

class Words_alphabet
Words_alphabet( self, alphabet)

sage: w = Words([1,2,3])
sage: w == loads(dumps(w))
True

Functions: count,$ \,$ iterator

count( self)

sage: Words([1,2,3]).count()
+Infinity

iterator( self)

sage: Words([1,2,3]).list() #indirect doctest
Traceback (most recent call last):
...
NotImplementedError

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

sage: 2 in Words([1,2,3])
False
sage: [2] in Words([1,2,3])
True
sage: [1, 'a'] in Words([1,2,3])
False

__repr__( self)

sage: Words([1,2,3]).__repr__()
'Words from the alphabet [1, 2, 3]'

Class: Words_alphabetk

class Words_alphabetk
Words_alphabetk( self, alphabet, k)

TESTS:

sage: w = Words([1,2,3], 2); w
Words from [1, 2, 3] of length 2
sage: w.count()
9

Functions: count,$ \,$ iterator

count( self)

Returns the number of words of length n from alphabet.

sage: Words(['a','b','c'], 4).count()
81
sage: Words(3, 4).count()
81
sage: Words(0,0).count()
1
sage: Words(5,0).count()
1
sage: Words(['a','b','c'],0).count()
1
sage: Words(0,1).count()
0
sage: Words(5,1).count()
5
sage: Words(['a','b','c'],1).count()
3
sage: Words(7,13).count()
96889010407L               # 32-bit
96889010407                # 64-bit
sage: Words(['a','b','c','d','e','f','g'],13).count()
96889010407L               # 32-bit
96889010407                # 64-bit

iterator( self)

Returns an iterator for all of the words of length k from alphabet. The iterator outputs the words in lexicographic order.

TESTS:

sage: [w for w in Words(['a', 'b'], 2)] 
[['a', 'a'], ['a', 'b'], ['b', 'a'], ['b', 'b']]
sage: [w for w in Words(['a', 'b'], 0)]
[[]]
sage: [w for w in Words([], 3)]
[]

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

sage: w = Words([1,2,3], 2)
sage: [1,2,3] in w
False
sage: [1,2] in w
True
sage: [3,4] in w
False

__repr__( self)

TESTS:

sage: repr(Words([1,2,3], 2))
'Words from [1, 2, 3] of length 2'

Class: Words_n

class Words_n
Words_n( self, n)

sage: w = Words(3)
sage: w == loads(dumps(w))
True

Functions: count,$ \,$ iterator

count( self)

sage: Words(3).count()
+Infinity

iterator( self)

sage: Words(3).list() #indirect doctest
Traceback (most recent call last):
...
NotImplementedError

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

sage: 2 in Words(3)
False
sage: [1,'a',3] in Words(3)
True
sage: [1,2] in Words(3)
False

__repr__( self)

sage: Words(3).__repr__()
'Words of length 3'

See About this document... for information on suggesting changes.