source: sage/combinat/word.py @ 7201:6dcae61ce5e6

Revision 7201:6dcae61ce5e6, 15.6 KB checked in by Mike Hansen <mhansen@…>, 6 years ago (diff)

Miscellaneaous combinatorics updates / fixes / additions.
Line 
1#*****************************************************************************
2#       Copyright (C) 2007 Mike Hansen <mhansen@gmail.com>,
3#
4#  Distributed under the terms of the GNU General Public License (GPL)
5#
6#    This code is distributed in the hope that it will be useful,
7#    but WITHOUT ANY WARRANTY; without even the implied warranty of
8#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
9#    General Public License for more details.
10#
11#  The full text of the GPL is available at:
12#
13#                  http://www.gnu.org/licenses/
14#*****************************************************************************
15
16import sage.combinat.generator as generator
17from sage.misc.mrange import xmrange
18import sage.combinat.permutation
19import itertools
20import __builtin__
21from combinat import CombinatorialClass, CombinatorialObject
22from sage.rings.all import binomial, Integer, infinity
23
24def Words(*args):
25    """
26    Returns the combinatorial class of words of length k
27    from alphabet.
28
29    EXAMPLES:
30        sage: w = Words([1,2,3], 2); w
31        Words from [1, 2, 3] of length 2
32        sage: w.count()
33        9
34        sage: w.list()
35        [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]
36    """
37    if len(args) == 0:
38        return Words_all()
39    elif len(args) == 1:
40        if isinstance(args[0], (int, Integer)):
41            return Words_n(args[0])
42        elif isinstance(args[0], list):
43            return Words_alphabet(args[0])
44    elif len(args) == 2:
45        if isinstance(args[0], (int, Integer)):
46            alphabet = range(1,args[0]+1)
47        else:
48            alphabet = args[0]
49        k = args[1]
50        return Words_alphabetk(alphabet, k)
51
52    raise ValueError, "do not know how to make a combinatorial class of words from %s"%args
53
54class Words_all(CombinatorialClass):
55    def __repr__(self):
56        return "Words"
57
58    def count(self):
59        return infinity
60
61    def __contains__(self, x):
62        return isinstance(x, list)
63
64    def list(self):
65        raise NotImplementedError
66
67    def iterator(self):
68        raise NotImplementedError
69   
70class Words_n(CombinatorialClass):
71    def __init__(self, n):
72        self.n = n
73       
74    def __repr__(self):
75        return "Words of length %s"%self.n
76
77    def count(self):
78        return infinity
79
80    def __contains__(self, x):
81        return isinstance(x, list) and len(x) == self.n
82
83    def list(self):
84        raise NotImplementedError
85
86    def iterator(self):
87        raise NotImplementedError       
88
89class Words_alphabet(CombinatorialClass):
90    def __init__(self, alphabet):
91        self.alphabet = alphabet
92       
93    def __repr__(self):
94        return "Words of from the alphabet %s"%self.alphabet
95
96    def count(self):
97        return infinity
98
99    def __contains__(self, x):
100        return isinstance(x, list) and all(map(lambda i: i in alphabet, x))
101
102    def list(self):
103        raise NotImplementedError
104
105    def iterator(self):
106        raise NotImplementedError     
107
108class Words_alphabetk(CombinatorialClass):
109    def __init__(self, alphabet, k):
110        """
111        TESTS:
112            sage: import sage.combinat.word as word
113            sage: w = word.Words_alphabetk([1,2,3], 2); w
114            Words from [1, 2, 3] of length 2
115            sage: w.count()
116            9
117        """
118        self.alphabet = alphabet
119        self.k = k
120
121    def __repr__(self):
122        """
123        TESTS:
124            sage: repr(Words([1,2,3], 2))
125            'Words from [1, 2, 3] of length 2'
126        """
127        return "Words from %s of length %s"%(self.alphabet, self.k)
128
129
130    def count(self):
131        r"""
132        Returns the number of words of length n from
133        alphabet.
134
135        EXAMPLES:
136            sage: Words(['a','b','c'], 4).count()
137            81
138            sage: Words(3, 4).count()
139            81
140            sage: Words(0,0).count()
141            1
142            sage: Words(5,0).count()
143            1
144            sage: Words(['a','b','c'],0).count()
145            1
146            sage: Words(0,1).count()
147            0
148            sage: Words(5,1).count()
149            5
150            sage: Words(['a','b','c'],1).count()
151            3
152            sage: Words(7,13).count()
153            96889010407L               # 32-bit
154            96889010407                # 64-bit
155            sage: Words(['a','b','c','d','e','f','g'],13).count()
156            96889010407L               # 32-bit
157            96889010407                # 64-bit
158        """
159        n = len(self.alphabet)
160        return n**self.k
161
162    def iterator(self):
163        """
164        Returns an iterator for all of the words
165        of length k from alphabet. The iterator
166        outputs the words in lexicographic order.
167
168        TESTS:
169            sage: [w for w in Words(['a', 'b'], 2)]
170            [['a', 'a'], ['a', 'b'], ['b', 'a'], ['b', 'b']]
171            sage: [w for w in Words(['a', 'b'], 0)]
172            [[]]
173            sage: [w for w in Words([], 3)]
174            []
175        """
176
177        n = len(self.alphabet)
178
179        if self.k == 0:
180            yield []
181            return
182
183        for w in xmrange([n]*self.k):
184            yield map(lambda x: self.alphabet[x], w)
185
186
187def alphabet_order(alphabet):
188    """
189    Returns the ordering function of the alphabet A.
190    The function takes two elements x and y of A and
191    returns True if x occurs before y in A.
192
193    EXAMPLES:
194        sage: f = word.alphabet_order(['a','b','c'])
195        sage: f('a', 'b')
196        True
197        sage: f('c', 'a')
198        False
199        sage: f('b', 'b')
200        False
201
202    """
203
204    return lambda x,y: alphabet.index(x) < alphabet.index(y)
205
206
207
208def standard(w, alphabet = None, ordering = None):
209    """
210    Returns the standard permutation of the word
211    w on the ordered alphabet.  It is defined as
212    the permutation with exactly the same number of
213    inversions as w.
214
215    By default, the letters are ordered using <.  A
216    custom ordering can be specified by passing an
217    ordering function into ordering.
218
219    EXAMPLES:
220        sage: word.standard([1,2,3,2,2,1,2,1])
221        [1, 4, 8, 5, 6, 2, 7, 3]
222    """
223
224    if alphabet == None:
225        alphabet = range(1,max(w)+1)
226       
227    if ordering == None:
228        ordering = lambda x,y: x < y
229
230    def ordering_cmp(x,y):
231        """
232        Returns -1 if x < y under ordering otherwise it returns 1.
233        """
234        if ordering(x,y):
235            return -1
236        else:
237            return 1
238
239
240    d = evaluation_dict(w)
241    keys = d.keys()
242    keys.sort(cmp=ordering_cmp)
243
244    offset = 0
245    temp = 0
246    for k in keys:
247        temp = d[k]
248        d[k] = offset
249        offset += temp
250
251    result = []
252    for l in w:
253        d[l] += 1
254        result.append(d[l])
255
256    return sage.combinat.permutation.Permutation(result)
257   
258   
259def evaluation_dict(w):
260    """
261    Returns a dictionary that represents the evalution
262    of the word w.
263
264    EXAMPLES:
265        sage: word.evaluation_dict([2,1,4,2,3,4,2])
266        {1: 1, 2: 3, 3: 1, 4: 2}
267        sage: d = word.evaluation_dict(['b','a','d','b','c','d','b'])
268        sage: map(lambda i: d[i], ['a','b','c','d'])
269        [1, 3, 1, 2]
270        sage: word.evaluation_dict([])
271        {}
272
273    """
274
275    d = {}
276    for l in w:
277        if l not in d:
278            d[l] = 1
279        else:
280            d[l] += 1
281
282    return d
283
284def evaluation_sparse(w):
285    """
286
287    EXAMPLES:
288        sage: word.evaluation_sparse([4,4,2,5,2,1,4,1])
289        [[1, 2], [2, 2], [4, 3], [5, 1]]
290    """
291    ed = evaluation_dict(w)
292    keys = ed.keys()
293    keys.sort()
294    return [[x, ed[x]] for x in keys]
295
296def evaluation_partition(w):
297    """
298    Returns the evaluation of the word w as a partition.
299
300    EXAMPLE:
301        sage: word.evaluation_partition([2,1,4,2,3,4,2])
302        [3, 2, 1, 1]
303    """
304
305    d = evaluation_dict(w)
306    p = d.values()
307    p.sort(reverse=True)
308    return p
309
310def evaluation(w, alphabet=None):
311    r"""
312    Returns the evalutation of the word as a list.
313    Either the word must be a word of integers or you
314    must provide the alphabet as a list.
315
316    EXAMPLES:
317        sage: word.evaluation(['b','a','d','b','c','d','b'],['a','b','c','d','e'])
318        [1, 3, 1, 2, 0]
319        sage: word.evaluation([1,2,2,1,3])
320        [2, 2, 1]
321    """
322
323    if alphabet == None:
324        if len(w) == 0:
325            alpha = 0
326        else:
327            alpha = max(w)
328
329        e = [0] * alpha
330
331        for letter in w:
332            e[letter-1] += 1
333        return e
334
335    else:
336        d = evaluation_dict(w)
337        e = [0] * len(alphabet)
338        indices = {}
339        for i in range(len(alphabet)):
340            indices[alphabet[i]] = i
341        for l in w:
342            if l in d:
343                e[indices[l]] += 1
344        return e
345
346def from_standard_and_evaluation(sp, e, alphabet=None):
347    """
348    Returns the word given by the standard permutation
349    sp and the evaluation e.
350
351    EXAMPLES:
352        sage: a = [1,2,3,2,2,1,2,1]
353        sage: e = word.evaluation(a)
354        sage: sp = word.standard(a)
355        sage: b = word.from_standard_and_evaluation(sp, e)
356        sage: b
357        [1, 2, 3, 2, 2, 1, 2, 1]
358        sage: a == b
359        True
360
361    """
362
363    if sum(e) != len(sp):
364        return
365
366    if alphabet == None:
367        alphabet = range(1, len(e)+1)
368    elif isinstance(alphabet,Integer):
369        alphabet = range(1, alphabet+1)
370
371    part_sum = 0
372    subs = []
373    word = sp[:]
374    for i in range(len(e)):
375        next_part_sum = part_sum + e[i]
376        for k in range(part_sum, next_part_sum):
377            subs.append([k+1,alphabet[i]])
378        part_sum = next_part_sum
379
380    for sub in subs:
381        word[word.index(sub[0])] = sub[1]
382
383    return word
384
385def swap(w,i,j=None):
386   """
387   Returns the word w with entries at positions i and
388   j swapped.  By default, j = i+1.
389
390   EXAMPLES:
391       sage: word.swap([1,2,3],0,2)
392       [3, 2, 1]
393       sage: word.swap([1,2,3],1)
394       [1, 3, 2]
395   """
396   if j == None:
397       j = i+1
398   new = w[:]
399   (new[i], new[j]) = (new[j], new[i])
400   return new
401
402def swap_increase(w, i):
403    """
404    Returns the word w with positions i and i+1 exchanged
405    if w[i] > w[i+1].  Otherwise, it returns w.
406
407    EXAMPLES:
408        sage: word.swap_increase([1,3,2],0)
409        [1, 3, 2]
410        sage: word.swap_increase([1,3,2],1)
411        [1, 2, 3]
412
413    """
414
415    if w[i] > w[i+1]:
416        return swap(w,i)
417    else:
418        return w
419
420def swap_decrease(w, i):
421    """
422    Returns the word w with positions i and i+1 exchanged
423    if w[i] < w[i+1].  Otherwise, it returns w.
424
425    EXAMPLES:
426        sage: word.swap_decrease([1,3,2],0)
427        [3, 1, 2]
428        sage: word.swap_decrease([1,3,2],1)
429        [1, 3, 2]
430
431    """
432
433    if w[i] < w[i+1]:
434        return swap(w,i)
435    else:
436        return w
437
438def lex_less(w1,w2):
439    """
440    Returns true if the word w1 is lexicographically
441    less than w2.  It is restricted to words whose
442    letters can be compared by <.
443
444    EXAMPLES:
445        sage: word.lex_less([1,2,3],[1,3,2])
446        True
447        sage: word.lex_less([3,2,1],[1,2,3])
448        False
449    """
450
451    i = 0
452    while (i <= len(w1) ) and (i <= len(w2)) and (w1[i] == w2[i]):
453        i += 1
454
455    if i > len(w2):
456        return False
457    if i > len(w1):
458        return True
459
460    return w1[i] < w2[i]
461
462def lex_cmp(w1,w2):
463    """
464    Returns -1 if the word w1 is lexicographically
465    less than w2; otherwise, it returns 1.
466    It is restricted to words whose
467    letters can be compared by <.
468
469    Useful to pass into Python's sort()
470
471    EXAMPLES:
472        sage: word.lex_cmp([1,2,3],[1,3,2])
473        -1
474        sage: word.lex_cmp([3,2,1],[1,2,3])
475        1
476    """
477    if lex_less(w1, w2):
478        return -1
479    else:
480        return 1
481
482def deg_lex_less(w1,w2):
483    """
484    Returns true if the word w1 is degree
485    lexicographically less than w2.  It is
486    restricted to words whose letters can be
487    compared by < as well as summed.
488
489    EXAMPLES:
490        sage: word.deg_lex_less([1,2,3],[1,3,2])
491        True
492        sage: word.deg_lex_less([1,2,4],[1,3,2])
493        False
494        sage: word.deg_lex_less([3,2,1],[1,2,3])
495        False
496    """
497
498    d1 = sum(w1)
499    d2 = sum(w2)
500
501    if d1 != d2:
502        return d1 < d2
503
504    return lex_less(w1,w2)
505
506def inv_lex_less(w1, w2):
507    """
508    Returns true if the word w1 is inverse
509    lexicographically less than w2.  It is
510    restricted to words whose letters can be
511    compared by <.
512
513    EXAMPLES:
514        sage: word.inv_lex_less([1,2,4],[1,3,2])
515        False
516        sage: word.inv_lex_less([3,2,1],[1,2,3])
517        True
518    """
519    if len(w1) != len(w2):
520        return len(w1) < len(w2)
521
522    for i in reversed(range(0,len(w1))):
523        if w1[i] != w2[i]:
524            return w1[i] < w2[i]
525
526    return False
527           
528
529
530def deg_inv_lex_less(w1,w2):
531    """
532    Returns true if the word w1 is degree inverse
533    lexicographically less than w2.  It is
534    restricted to words whose letters can be
535    compared by < as well as summed.
536
537    EXAMPLES:
538        sage: word.deg_inv_lex_less([1,2,4],[1,3,2])
539        False
540        sage: word.deg_inv_lex_less([3,2,1],[1,2,3])
541        True
542    """
543
544    d1 = sum(w1)
545    d2 = sum(w2)
546
547    if d1 != d2:
548        return d1 < d2
549
550    return inv_lex_less(w1,w2)
551
552
553def rev_lex_less(w1,w2):
554    """
555    Returns true if the word w1 is reverse
556    lexicographically less than w2.  It is
557    restricted to words whose letters can be
558    compared by <.
559
560    EXAMPLES:
561        sage: word.rev_lex_less([1,2,4],[1,3,2])
562        True
563        sage: word.rev_lex_less([3,2,1],[1,2,3])
564        False
565    """
566
567    if len(w1) != len(w2):
568        return len(w1) > len(w2)
569
570    for i in reversed(range(0,len(w1))):
571        if w1[i] != w2[i]:
572            return w1[i] > w2[i]
573
574    return False
575
576
577def deg_rev_lex_less(w1, w2):
578    """
579    Returns true if the word w1 is degree reverse
580    lexicographically less than w2.  It is
581    restricted to words whose letters can be
582    compared by < as well as summed.
583
584    EXAMPLES:
585        sage: word.deg_rev_lex_less([1,2,4],[1,3,2])
586        False
587        sage: word.deg_rev_lex_less([3,2,1],[1,2,3])
588        False
589    """
590
591    d1 = sum(w1)
592    d2 = sum(w2)
593
594    if d1 != d2:
595        return d1 < d2
596
597    return rev_lex_less(w1,w2)
598
599
600def min_lex(l):
601    """Returns the minimal element in lexicographic
602    order of a l of words.
603
604    EXAMPLES:
605        sage: word.min_lex([[1,2,3],[1,3,2],[3,2,1]])
606        [1, 2, 3]
607    """
608
609    if len(l) == 0:
610        return None
611    new_l = l[:]
612    new_l.sort(cmp=lex_cmp)
613    return new_l[0]
614
615
616###################
617# Shuffle Product #
618###################
619
620
621## def shuffle(w1,w2):
622##     """
623##     Returns the list of words in the shuffle product
624##     of w1 and w2.
625
626##     """
627##     return shuffle_list(w1,w2)
628
629## def shuffle_shifted(w1, w2):
630##     """
631##     Returns the shifted shuffle of w1 and w2.
632
633##     EXAMPLES:
634
635##     """
636
637##     return shuffle(w1, [x+len(w1) for x in v])
638
639## def shuffle_count(w1,w2):
640##     """
641##     Returns the number of words in the shuffle product
642##     of w1 and w2.
643
644##     It is given by binomial(len(w1)+len(w2), len(w1)).
645
646##     EXAMPLES:
647##         sage: word.shuffle_count([2,3],[3,4])
648##         6
649##     """
650
651##     return binomial(len(w1)+len(w2), len(w1))
652   
653
654## def shuffle_list(w1,w2):
655##     """
656##     Returns the list of words in the shuffle product
657##     of w1 and w2.
658
659##     """
660
661##     return [w for w in shuffle_iterator(w1,w2)]
662
663## def shuffle_iterator(w1,w2):
664##     """
665##     Returns an iterator for the words in the
666##     shuffle product of w1 and w2.
667
668##     EXAMPLES:
669   
670##     """
671
672##     n1 = len(w1)
673##     n2 = len(w2)
674
675##     def proc(vect):
676##         i1 = -1
677##         i2 = -1
678##         res = []
679##         for v in vect:
680##             if v == 1:
681##                 i1 += 1
682##                 res.append(w1[i1])
683##             else:
684##                 i2 += 1
685##                 res.append(w2[i2])
686
687##     return itertools.imap(proc, integer_vector.iterator(n1, n1+n2, max_parts=1))
Note: See TracBrowser for help on using the repository browser.