Module: sage.combinat.word
Words
Module-level Functions
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]]
) |
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) |
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
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
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
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
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
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]
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([]) {}
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]
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]]
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
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
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
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
l) |
sage: import sage.combinat.word as word sage: word.min_lex([[1,2,3],[1,3,2],[3,2,1]]) [1, 2, 3]
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
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]
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]
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]
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]
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]
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
self, w1, w2) |
sage: s = ShuffleProduct([1,2],[3,4],overlapping=True) sage: s == loads(dumps(s)) True
Functions: 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__
self) |
sage: ShuffleProduct([1,2],[3,4],overlapping=True).__repr__() 'Overlapping shuffle product of [1, 2] and [3, 4]'
Class: ShuffleProduct_overlapping_r
self, w1, w2, r) |
sage: s = ShuffleProduct([1,2],[3,4], overlapping=1) sage: s == loads(dumps(s)) True
Functions: 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__
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
self, w1, w2) |
sage: s = ShuffleProduct([1,2],[3,4], shifted=True) sage: s == loads(dumps(s)) True
Special Functions: __init__,
__repr__
self) |
sage: ShuffleProduct([1,2],[3,4], shifted=True).__repr__() 'Shifted shuffle product of [1, 2] and [5, 6]'
Class: ShuffleProduct_w1w2
self, w1, w2) |
sage: s = ShuffleProduct([1,2],[3,4]) sage: s == loads(dumps(s)) True
Functions: count,
iterator
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
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
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
self) |
sage: repr(ShuffleProduct([1,2],[3,4])) 'Shuffle product of [1, 2] and [3, 4]'
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
Functions: count,
iterator
self) |
sage: Words().count() +Infinity
self) |
sage: Words().list() #indirect doctest Traceback (most recent call last): ... NotImplementedError
Special Functions: __contains__,
__repr__
self, x) |
sage: 2 in Words() False sage: [1,2] in Words() True
self) |
sage: Words().__repr__() 'Words'
Class: Words_alphabet
self, alphabet) |
sage: w = Words([1,2,3]) sage: w == loads(dumps(w)) True
Functions: count,
iterator
self) |
sage: Words([1,2,3]).count() +Infinity
self) |
sage: Words([1,2,3]).list() #indirect doctest Traceback (most recent call last): ... NotImplementedError
Special Functions: __contains__,
__init__,
__repr__
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
self) |
sage: Words([1,2,3]).__repr__() 'Words from the alphabet [1, 2, 3]'
Class: 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
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
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__
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
self) |
TESTS:
sage: repr(Words([1,2,3], 2)) 'Words from [1, 2, 3] of length 2'
Class: Words_n
self, n) |
sage: w = Words(3) sage: w == loads(dumps(w)) True
Functions: count,
iterator
self) |
sage: Words(3).count() +Infinity
self) |
sage: Words(3).list() #indirect doctest Traceback (most recent call last): ... NotImplementedError
Special Functions: __contains__,
__init__,
__repr__
self, x) |
sage: 2 in Words(3) False sage: [1,'a',3] in Words(3) True sage: [1,2] in Words(3) False
self) |
sage: Words(3).__repr__() 'Words of length 3'
See About this document... for information on suggesting changes.