Hi Nicolas,
> I just finished rebasing the Sage-Combinat patches for 4.1.1. They
> seem to still work on 4.1. Let me know if you run into any problem!
The patches still work for me with sage-4.1, but with sage-4.1.1 I get the
following error:
Current non version guards:
Updated non version guards:
Skip backward compatibility patches for sage 3.4.1
Skip backward compatibility patches for sage 3.4.2
Skip backward compatibility patches for sage 4.0
Skip backward compatibility patches for sage 4.0.1
Skip backward compatibility patches for sage 4.0.2
Skip backward compatibility patches for sage 4.1
Skip backward compatibility patches for sage 4.1.1
Keep backward compatibility patches for sage 4.1.2
Updating guards
/Applications/sage-4.1.1/sage -hg --config 'extensions.hgext.mq=' qselect -q
-n
/Applications/sage-4.1.1/sage -hg --config 'extensions.hgext.mq=' qselect
4_1_2
number of unguarded, unapplied patches has changed from 91 to 92
/Applications/sage-4.1.1/sage -hg --config 'extensions.hgext.mq=' qpush
trac_6627-lyndon_words_fix.patch
applying trac_6253-constant_function-nt.patch
applying trac_6641-poset_antichains_backtracker.patch
applying trac_6641-poset_antichains_backtracker-part2.patch
applying trac_6627-lyndon_words_fix.patch
patching file sage/combinat/words/word.py
Hunk #1 FAILED at 156
Hunk #2 FAILED at 3339
Hunk #3 FAILED at 3418
Hunk #4 FAILED at 4078
Hunk #5 FAILED at 5266
Hunk #6 FAILED at 5280
Hunk #7 FAILED at 5304
Hunk #8 succeeded at 3633 with fuzz 2 (offset -1694 lines).
Hunk #9 FAILED at 5714
8 out of 9 hunks FAILED -- saving rejects to file
sage/combinat/words/word.py.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
Errors during apply, please fix and refresh trac_6627-lyndon_words_fix.patch
Abort
--- word.py
+++ word.py
@@ -157,9 +157,9 @@
::
sage: print w.lyndon_factorization()
- (ab.aabbb.a)
+ (ab, aabbb, a)
sage: print w.crochemore_factorization()
- (a.b.a.ab.bb.a)
+ (a, b, a, ab, bb, a)
::
@@ -3340,69 +3340,6 @@
return False
return True
- def _duval_algorithm(self):
- r"""
- TESTS::
-
- sage: Word('010010010001000')._duval_algorithm()
- (01.001.001.0001)
- sage: Word('122113112212')._duval_algorithm()
- (122.113.112212)
-
- REFERENCES:
-
- - [1] J.-P. Duval, Factorizing words over an ordered alphabet,
- J. Algorithms 4 (1983), no. 4, 363--381.
- """
- t = Factorization()
- cm = self
- c = iter(cm.to_integer_word())
- cc = iter(cm.to_integer_word())
- cc.next()
- i = 0
- d = 1
- j = k = 1
- l = len(cm)
-
- while k < l:
- c, c_s = tee(c)
- c_s = c_s.next()
- cc, cc_s = tee(cc)
- cc_s = cc_s.next()
- if c_s < cc_s:
- cc.next()
- k += 1
- j = k
- d = k - i
- c = iter(cm.to_integer_word())
- elif c_s == cc_s:
- cc.next()
- k += 1
- if (k - j) == d:
- j = k
- c = iter(cm.to_integer_word())
- else:
- c.next()
- else:
- i += d
- while i <= j:
- i += d
- t.append(cm[:d])
- cm = cm[d:]
- c = iter(cm.to_integer_word())
- cc = iter(cm.to_integer_word())
- cc.next()
- i = j
- j += 1
- k = j
- d = 1
- i += d
- while i <= j:
- i += d
- t.append(cm[:d])
- cm = cm[d:]
- return t
-
def lyndon_factorization(self):
r"""
Returns the Lyndon factorization of self.
@@ -3419,37 +3356,65 @@
EXAMPLES::
sage: Word('010010010001000').lyndon_factorization()
- (01.001.001.0001.0.0.0)
+ (01, 001, 001, 0001, 0, 0, 0)
sage: Words('10')('010010010001000').lyndon_factorization()
- (0.10010010001000)
+ (0, 10010010001000)
sage: Word('abbababbaababba').lyndon_factorization()
- (abb.ababb.aababb.a)
+ (abb, ababb, aababb, a)
sage: Words('ba')('abbababbaababba').lyndon_factorization()
- (a.bbababbaaba.bba)
-
- TESTS::
-
+ (a, bbababbaaba, bba)
+ sage: Word([1,2,1,3,1,2,1]).lyndon_factorization()
+ (1213, 12, 1)
+
+ TESTS::
+
+ sage: Words('01')('').lyndon_factorization()
+ ()
sage: Word('01').lyndon_factorization()
(01)
sage: Words('10')('01').lyndon_factorization()
- (0.1)
+ (0, 1)
sage: lynfac = Word('abbababbaababba').lyndon_factorization()
sage: [x.is_lyndon() for x in lynfac]
[True, True, True, True]
sage: lynfac =
Words('ba')('abbababbaababba').lyndon_factorization()
sage: [x.is_lyndon() for x in lynfac]
[True, True, True]
-
+ sage: w = words.ThueMorseWord()[:1000]
+ sage: w == prod(w.lyndon_factorization())
+ True
+
REFERENCES:
- [1] J.-P. Duval, Factorizing words over an ordered alphabet,
J. Algorithms 4 (1983) 363--381.
- """
- tab = self._duval_algorithm()
- l = sum(len(x) for x in tab)
- if l < self.length():
- tab += self[l:]._duval_algorithm()
- return tab
+
+ - [2] G. Melancon, Factorizing infinite words using Maple,
+ MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42.
+
+ """
+ cmp = self.parent().cmp_letters
+ # We compute the indexes of the factorization.
+ n = self.length()
+ k = -1
+ F = [0]
+ while k < n-1:
+ i = k+1
+ j = k+2
+ while j < n:
+ c = cmp(self[i], self[j])
+ if c < 0:
+ i = k+1
+ j += 1
+ elif c == 0:
+ i += 1
+ j += 1
+ else:
+ break
+ while k < i:
+ F.append(k + j - i + 1)
+ k = k + j - i
+ return Factorization([self[F[i]:F[i+1]] for i in range(len(F)-1)])
def inversions(self):
r"""
@@ -4079,17 +4044,17 @@
sage: x = Word('abababb')
sage: x.crochemore_factorization()
- (a.b.abab.b)
+ (a, b, abab, b)
sage: mul(x.crochemore_factorization()) == x
True
sage: y = Word('abaababacabba')
sage: y.crochemore_factorization()
- (a.b.a.aba.ba.c.ab.ba)
+ (a, b, a, aba, ba, c, ab, ba)
sage: mul(y.crochemore_factorization()) == y
True
sage: x = Word([0,1,0,1,0,1,1])
sage: x.crochemore_factorization()
- (0.1.0101.1)
+ (0, 1, 0101, 1)
sage: mul(x.crochemore_factorization()) == x
True
@@ -5267,7 +5232,7 @@
The *standard factorization* of a word `w` is the unique
factorization: `w = uv` where `v` is the longest proper suffix
- of `w` that qualifies as a Lyndon word.
+ of `w` that is a Lyndon word.
Note that if `w` is a Lyndon word with standard factorization
`w = uv`, then `u` and `v` are also Lyndon words and `u < v`.
@@ -5281,21 +5246,25 @@
EXAMPLES::
sage: Words('01')('0010110011').standard_factorization()
- (001011.0011)
+ (001011, 0011)
sage: Words('123')('1223312').standard_factorization()
- (12233.12)
+ (12233, 12)
+ sage: Word([3,2,1]).standard_factorization()
+ (32, 1)
+ sage: Words('123')('').standard_factorization()
+ ()
::
sage: w = Word('0010110011',alphabet='01')
sage: w.standard_factorization()
- (001011.0011)
+ (001011, 0011)
sage: w = Word('0010110011',alphabet='10')
sage: w.standard_factorization()
- (0010110011.)
+ (001011001, 1)
sage: w = Word('1223312',alphabet='123')
sage: w.standard_factorization()
- (12233.12)
+ (12233, 12)
REFERENCES:
@@ -5305,13 +5274,13 @@
- [2] J.-P. Duval, Factorizing words over an ordered alphabet,
J. Algorithms 4 (1983) 363--381.
"""
- suff = self[1:]
+ if self.is_empty():
+ return Factorization([])
for l in xrange(1, self.length()):
- pref = self[:l]
- if pref.is_lyndon() and suff.is_lyndon():
- return Factorization([pref, suff])
- suff = suff[1:]
- return Factorization([self, self.parent()()])
+ suff = self[l:]
+ if suff.is_lyndon():
+ return Factorization([self[:l], suff])
+ raise RuntimeError, 'Bug in standard factorization of words'
def standard_factorization_of_lyndon_factorization(self):
r"""
@@ -5715,9 +5684,9 @@
sage: sage.combinat.words.word.Factorization()
()
sage: sage.combinat.words.word.Factorization([Word('ab'),
Word('ba')])
- (ab.ba)
- """
- return '(%s)' % '.'.join(w.string_rep() for w in self)
+ (ab, ba)
+ """
+ return '(%s)' % ', '.join(w.string_rep() for w in self)
class CallableFromListOfWords(tuple):
r"""
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en
-~----------~----~----~----~------~----~------~--~---
