Opened 8 years ago
Closed 7 years ago
#16926 closed enhancement (fixed)
Merge the features of SymmetricGroupAlgebra and SymmetricGroup.algebra
Reported by:  nthiery  Owned by:  

Priority:  major  Milestone:  sage6.6 
Component:  combinatorics  Keywords:  days64 
Cc:  sagecombinat, tscrim, darij, virmaux  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Darij Grinberg, Nicolas M. Thiéry 
Report Upstream:  N/A  Work issues:  
Branch:  bf9fc43 (Commits, GitHub, GitLab)  Commit:  bf9fc43cd076381692686dbe26f66a61f7955c1a 
Dependencies:  #17981  Stopgaps: 
Description (last modified by )
We have different implementations of the algebra of the symmetric group, and more may come in the future:
SymmetricGroupAlgebra(K, n)
SymmetricGroup(n).algebra(K)
WeylGroup(['A',3]).algebra(K)
 ...
They mostly differ in how the elements of the symmetric group are represented, and each representation can have its advantage depending on the application in mind. So it's fine to keep them all. On the other hand, currently only the first one makes use of the special features of the symmetric group. After a discussion, we came up with a plan to share those features across all implementations:
 Make the categories and functionality as coherent as possible.
 Have
SymmetricGroupAlgebra
take an optional input for the index set.
Change History (74)
comment:1 Changed 8 years ago by
 Description modified (diff)
comment:2 followup: ↓ 3 Changed 8 years ago by
comment:3 in reply to: ↑ 2 Changed 8 years ago by
Replying to darij:
I don't even know how this is going to happen. AlgebraWithBases?? Coercions back and forth?
Later on, it could make sense to connect by coercions and an AlgebraWithBases
, but we don't need this for now. Each implementation would be standalone, just sharing common features through a common abstract class (in the category SymmetricGroups?().Algebras(...)).
comment:4 followup: ↓ 5 Changed 8 years ago by
Isn't that harder? There'd be quite a lot of functionality to triplicate...
comment:5 in reply to: ↑ 4 Changed 8 years ago by
Replying to darij:
Isn't that harder? There'd be quite a lot of functionality to triplicate...
You mean, harder with just the SymmetricGroups.Algebra
approach?
There is nothing to triplicate in this approach. Everything common is implemented exactly once, in SymmetricGroups?.Algebra.
comment:6 followup: ↓ 7 Changed 8 years ago by
Oh, you want to move things like the YoungJucysMurphy elements and the seminormal basis to an abstract base class?
Good idea actually, as long as we can ensure this doesn't slow them down on the standard SymmetricGroupAlgebra?.
comment:7 in reply to: ↑ 6 Changed 8 years ago by
Replying to darij:
Oh, you want to move things like the YoungJucysMurphy elements and the seminormal basis to an abstract base class?
Precisely.
Good idea actually, as long as we can ensure this doesn't slow them down on the standard SymmetricGroupAlgebra?.
That's something to be checked, but a priori given the kind of algorithms, I doubt it would.
comment:8 followup: ↓ 11 Changed 8 years ago by
I second using an ABC rather than a category. Also as mentioned in my comment on #16925, I think SymmetricGroupAlgebra
should actually use the group an an indexing set for the basis, thus keeping that as SymmetricGroup(n).algebra(K)
(alternatively merging in the general GroupAlgebra
implementation).
comment:9 followup: ↓ 10 Changed 8 years ago by
But we absolutely need to keep the SGA(p)
syntax working for SGA
a symmetric group algebra and p
a permutation. And we'd do well to not slow it down by any significant amount.
comment:10 in reply to: ↑ 9 Changed 8 years ago by
Replying to darij:
But we absolutely need to keep the
SGA(p)
syntax working forSGA
a symmetric group algebra andp
a permutation. And we'd do well to not slow it down by any significant amount.
I agree (and this is easy enough to do with _element_constructor_
). In fact, using the gap group, we'll significantly speed up the multiplication. Perhaps being clever by using a hybrid approach, we can speed up computing the basis too (IDK yet, haven't tried).
comment:11 in reply to: ↑ 8 Changed 8 years ago by
Replying to tscrim:
I second using an ABC rather than a category.
The category is doing just that: providing an ABC. Granted, it might look a bit overkill since we might not need an ABC for the elements or other functorial constructions. But in exchange (S_n).algebra() is automatically made to inherit from the ABC in a way that is uniform with all the other stuff about XXX algebras: no need to insert manually that ABC in SymmetricGroup.algebra
.
comment:12 Changed 8 years ago by
I don't really like the idea of putting into a category as opposed to having a proper ABC. Doing with an ABC means we can have automatic coercion by just doing:
def _coerce_map_from_(self, X): if isinstance(X, SGA_abstract): return True return super(SGA_abstract, self)._coerce_map_from_(X)
(We can't do this with categories, nor do I think we should for that matter.)
Also as you mentioned, it's overkill to me. Also if we were to have this in the category, we'd still have to override the algebra
method (or worse, a check on the group in the generic group algebra). Although I'm still of the opinion that we should merge the generic group algebra of S_{n} into SymmetricGroupAlgebra
and get that to work. I'm not sure what we'll need/want to do w.r.t. the Weyl group one, I haven't thought about how this will figure in yet.
Also since this is the same object in the "same" realization, IMO the WithRealizations
framework shouldn't be used here either. It also possible to convince to go this route, but I don't really think it'll be the best way.
comment:13 Changed 8 years ago by
Silly question, no doubt, but what is an ABC?
comment:14 Changed 8 years ago by
An Abstract Base Class.
comment:15 Changed 8 years ago by
 Branch set to public/combinat/fix_sga16926
 Cc virmaux added
 Commit set to f15f40cd95cd94cd3e4a3b843fd0b257746d43f0
 Description modified (diff)
 Status changed from new to needs_review
Okay, done. So some notes for the reviewer:
 Currently
descents
behavior differs from that given by the category, so as to avoid backwards incompatible change, we leave warning messages and leave the behavior alone.
reduced_word()
does not respect the order of multiplication and needs to be fixed so thatTestSuite
passes.
 I've added as much common functionality between
SymmetricGroup
andPermutations
since the former is a gap version of the latter. I'm leavingWeylGroup
alone because it is a matrix group, but if someone wants to add better support for conjugacy classes, then go ahead.
 I made a bunch of other optimizations for iterating over elements and microoptimizations.
 I abstracted
StandardPermutations_n
to better reflect the mathematics.
 Better and more careful handling of parents during multiplication.
 The
from_*
now can take a parent as input to better control their output (this was needed).
Some todo's for later:
 Improve the speed of multiplying Sage permutations:
sage: S = SymmetricGroup(5) sage: R = S.simple_reflections() sage: %timeit prod(R) 10000 loops, best of 3: 36.6 µs per loop sage: P = Permutations(5) sage: R = P.simple_reflections() sage: %timeit prod(R) 1000 loops, best of 3: 413 µs per loop
 Refactor the
Permutation
class to better be an element class, especially parsing of input (hard and tedious).
 Fix the issues noted above (also hard).
However, IMO the current version should be reviewed and included into Sage (as it is needed for #11111).
This is the other option, which I am keeping here for the official record:
 Create a category
SymmetricGroups
. Put the relevant groups in this category.  Generalize the features (YucisMurphy elements, ...) from
SymmetricGroupAlgebra
to the categorySymmetricGroups.Algebras
.  Put
SymmetricGroupAlgebra
in this category, and strip away all the code that is not needed anymore.  Cross ref the different implementations in the documentation.
New commits:
8144d47  Added optional argument for indexing set of SGA.

a2d9dcd  Initial setting of StandardPermutations_n to be in FiniteWeylGroups.

765cbdb  Fixes and tweaks and speedups.

a63dfd3  Added support for conjugacy classes for permutation groups.

f15f40c  Some additional fixes and cleanup.

comment:16 followup: ↓ 18 Changed 8 years ago by
Not sure if I'm going to be reviewing this (time is short as usual and I'm still not good at OOP  case in point, I don't know what mixins are for), but a few remarks.
First, a trivial group needs no generators. So this
+ if self.n <= 1: + return (self.one(),)
can be replaced by
+ if self.n <= 1: + return ()
Second, you are testing for the orderofmultiplication global in has_left_descent
and in has_right_descent
. I understand the reasoning behind it, but I don't like it, as it spreads a bad design choice further. Can we agree that the "left" in "left descent" stands for "left action" rather than "multiplying with s_i from the left", or is this too revisionistic?
comment:17 Changed 7 years ago by
 Commit changed from f15f40cd95cd94cd3e4a3b843fd0b257746d43f0 to 6597e7936048b8f30018a5e4a6e566836f6e5e68
comment:18 in reply to: ↑ 16 Changed 7 years ago by
Replying to darij:
Not sure if I'm going to be reviewing this (time is short as usual and I'm still not good at OOP  case in point, I don't know what mixins are for), but a few remarks.
I appreciate any time you can devote, plus I'd think it would be best that Nicolas takes a good look at this patch (and possibly have Aladin merge it into his current version of #11111 and test it there too).
(Mixins are as they sound to be, they are classes you "mix in" the class heirarchy which typically contain general or independent features. This SO thread I think gives a good overview of them.)
First, a trivial group needs no generators. ...
Good point; fixed.
Second, you are testing for the orderofmultiplication global in
has_left_descent
and inhas_right_descent
. I understand the reasoning behind it, but I don't like it, as it spreads a bad design choice further. Can we agree that the "left" in "left descent" stands for "left action" rather than "multiplying with s_i from the left", or is this too revisionistic?
It breaks the generic implementation of the long_element
method, which relies on the multiplication on the left corresponding to has_left_descent
. I feel these changes further shows permutation.py
can be a minefield...but I'm trying to make do with what I have.
comment:19 Changed 7 years ago by
Hello,
I would love to try to merge into #11111 but this last one cause too many merge conflicts. And some requiere more knowledge than I actually have in order to be solved (in particular those in set.py and integer_ring.py).
comment:20 Changed 7 years ago by
Shouldn't the __contains__
and __iter__
methods on StandardPermutations_n_abstract
be in StandardPermutations_n
instead? (Not sure about the other methods.) I find it strange to see an ABC whose most methods are anything but abstract.
comment:21 Changed 7 years ago by
 Commit changed from 6597e7936048b8f30018a5e4a6e566836f6e5e68 to 18b3441e41e0f30b6bc02bd5a746096b17189e27
Branch pushed to git repo; I updated commit sha1. New commits:
18b3441  Using itertools and moved methods from n_abstract.

comment:22 Changed 7 years ago by
__contains__
is a definite no because the subclasses want that to use that check. However, I moved __iter__
and a bunch of other methods to StandardPermutations_n
since they were (potentially) giving wrong results. I also used itertools
for the iteration because it was ~20x faster:
sage: %timeit len(list(itertools.permutations(range(1,6), 5))) 10000 loops, best of 3: 36.5 µs per loop sage: %timeit len(list(Permutations_set._fast_iter(range(1,6)))) 1000 loops, best of 3: 658 µs per loop
comment:23 followup: ↓ 24 Changed 7 years ago by
That's a nice find you made in the itertools. Good to see that "fast" iterator gone!
I'll shortly push my "fix" to the l2r/r2l issue. But meanwhile, I disagree about __contains__
. This method tests containment in Permutations(n), not in whatever subclass we have inherit from StandardPermutations_n_abstract
. If it stays in the ABC, then every subclass that does not override it will have a wrong __contains__
test. If you just want to be able to use it out of subclasses, why not @classmethod or @staticmethod?
comment:24 in reply to: ↑ 23 Changed 7 years ago by
Replying to darij:
But meanwhile, I disagree about
__contains__
. This method tests containment in Permutations(n), not in whatever subclass we have inherit fromStandardPermutations_n_abstract
. If it stays in the ABC, then every subclass that does not override it will have a wrong__contains__
test. If you just want to be able to use it out of subclasses, why not @classmethod or @staticmethod?
It would potentially give false positives, but it's better than the generic one from Parent
(which is part of the test):
sage: P = Permutations(5, avoiding=[1,4,2,3]) sage: P([1,4,2,3,5]) in P True
The idea is to override it for extra information and to include a super call so as to avoid duplicating code (i.e., this is good OOP).
comment:25 Changed 7 years ago by
 Commit changed from 18b3441e41e0f30b6bc02bd5a746096b17189e27 to f1202558f449a7797c86143a59e5c3e32a5349d8
comment:26 Changed 7 years ago by
Ah, if it was already semibroken this way, then it's fine. I've added a warning in the doc, however.
Not a review yet, but just a patch for the 'mult' issue. Are you OK with it?
comment:27 Changed 7 years ago by
Yes, it works for me.
comment:28 Changed 7 years ago by
 Commit changed from f1202558f449a7797c86143a59e5c3e32a5349d8 to caf4f43a19035e37cb4b4c67f0f040af84783c9e
Branch pushed to git repo; I updated commit sha1. New commits:
caf4f43  some more edits

comment:29 Changed 7 years ago by
Part of the review done (sorry, I'm slow). I fear I need explanations on this:
+ def __mul__(self, other): + r""" + Multiply ``self`` and ``other``. + + EXAMPLES:: + + sage: P = Permutations(4) + sage: P.simple_reflection(1) * Permutation([6,5,4,3,2,1]) + [5, 6, 4, 3, 2, 1] + """ + if (not isinstance(other, StandardPermutations_n.Element) + or self.parent() != other.parent()): + return Permutation.__mul__(self, other) + return self._mul_(other) + + def _mul_(self, other): + r""" + Multiply ``self`` and ``other``. + + EXAMPLES:: + + sage: P = Permutations(4) + sage: P.prod(P.gens()).parent() is P + True + """ + p = list(Permutation.__mul__(self, other)) + return self.__class__(self.parent(), p)
or someone else will have to vow for its correctness.
comment:30 Changed 7 years ago by
 Commit changed from caf4f43a19035e37cb4b4c67f0f040af84783c9e to f38fe13587fac895809d5f9d5fcf21b12bd23f0a
Branch pushed to git repo; I updated commit sha1. New commits:
f38fe13  I don't understand the index_set argument, and it is used incorrectly here  the retract methods are supposed to go into a different SGA, and making it have the same index_set as the domain causes bugs

comment:31 Changed 7 years ago by
Not done yet (symgp_conjugacy_class.py remains), but there are some things I don't get about this that I'd prefer to have answered before I go on.
 The _mul_ issue, as above.
 The meaning of the index_set parameter: is it just there to allow building the symmetric group algebra with different basis keys?
 _coerce_map_from_ claims that there exists a coercion from
SymmetricGroup(3).algebra(QQ)
toSymmetricGroupAlgebra(QQ, 3)
, but applying this coercion to elements fails. This is becauseStandardPermutations_n_abstract.__call__
does not take a permutation group element as a parameter. I am not sure what to do about it, since I wouldn't be happy with ducktyping in that constructor.
 Various methods don't work for
SymmetricGroup(3).algebra(QQ)
, and the fix is not as simple as addingindex_set=self.basis().keys()
.
comment:32 Changed 7 years ago by
 Dependencies set to #17981
I am implementing a coercion map from SymmetricGroup
to Permutations(n)
, and I need #17981 since I am having _coerce_map_from_
return a lambda function representing the coercion map. Changes coming shortly.
comment:33 Changed 7 years ago by
 Commit changed from f38fe13587fac895809d5f9d5fcf21b12bd23f0a to d4568f6e72f40500e1a39d56b4a4f74146fcab29
Branch pushed to git repo; I updated commit sha1. New commits:
cd15df4  Merge branch 'develop' into public/combinat/fix_sga16926

d01b36d  Merge branch 'develop' into public/combinat/fix_sga16926

0c95381  Merge branch 'develop' into public/combinat/fix_sga16926

cb7e154  Some fixing of the index_set options.

c9ebdd7  Implement coerce map for Permutations(n).

b0973dc  Fix coercion map when _coerce_map_from_ returns a callable.

bd0fcd1  Merge branch 'public/coerce/fix_coerce_map_from_callable' into public/combinat/fix_sga16926

d4568f6  Finish implementing coercion maps from SymmetricGroup to Permutations(n).

comment:34 Changed 7 years ago by
 Commit changed from d4568f6e72f40500e1a39d56b4a4f74146fcab29 to 9666765a5d7cbab9bfb2b284017fc15be0ab1518
Branch pushed to git repo; I updated commit sha1. New commits:
9666765  Allowing methods to work for other indexing sets.

comment:35 Changed 7 years ago by
So the coercion now worked with my changes to having a coercion from the indexing sets, but a bunch of methods were broken using SymmetricGroup(n)
. I've fixed this by casting the elements into a Permutations(n)
element (essentially a Permutation
instance), which may not be the fastest for elements of SymmetricGroup(n)
, but it works and generalized (when there is a conversion) and is still very fast for elements of Permutations(n)
. However, IMO other indexing sets (such as with a WeylGroup
) can wait for later since they just use the general GroupAlgebra
class.
comment:36 followup: ↓ 38 Changed 7 years ago by
Should not algebra_generators return a Family instead of a list ?
comment:37 Changed 7 years ago by
 Commit changed from 9666765a5d7cbab9bfb2b284017fc15be0ab1518 to 7daaa83ee93aace69ce63e3ad80d1c5e43f5cdd7
Branch pushed to git repo; I updated commit sha1. New commits:
7daaa83  Made algebra_generators return a Family.

comment:38 in reply to: ↑ 36 Changed 7 years ago by
Replying to virmaux:
Should not algebra_generators return a Family instead of a list ?
Although this was the current implementation, I think this is a good as time as any to make this change. Ducktyping and how Family
works means this shouldn't break anyone's code.
comment:39 Changed 7 years ago by
 Commit changed from 7daaa83ee93aace69ce63e3ad80d1c5e43f5cdd7 to f11ba248bd9cf4e88949cb628fa38063b04c0787
Branch pushed to git repo; I updated commit sha1. New commits:
f11ba24  further corrections in SymmetricGroupAlgebra

comment:40 Changed 7 years ago by
 Commit changed from f11ba248bd9cf4e88949cb628fa38063b04c0787 to de5eb2ffa58726499d0c2a6a396d1bdcc9fedfbc
Branch pushed to git repo; I updated commit sha1. New commits:
de5eb2f  more fixes & warnings

comment:41 Changed 7 years ago by
 Commit changed from de5eb2ffa58726499d0c2a6a396d1bdcc9fedfbc to d097fdf6dc78cf7c1bc97781062bd22418f8d8ef
Branch pushed to git repo; I updated commit sha1. New commits:
d097fdf  review complete(?):

comment:42 Changed 7 years ago by
 Commit changed from d097fdf6dc78cf7c1bc97781062bd22418f8d8ef to 6657c31932284db43898aee3dc33ca3f5558b544
Branch pushed to git repo; I updated commit sha1. New commits:
6657c31  what subsets?

comment:43 Changed 7 years ago by
I'm done reviewing the functionality of this patch  it is a good step forward, although I wish it would address the problem in a more systematic way (e.g., using AlgebraWithRealizations
to put the different bases and indexing sets for the symmetric group algebra on equal footing, and also to get rid of the accursed mult
global variable). It doesn't introduce any new technical debt, though, that's for sure, and it cleans up some of the existing.
On the other hand, I cannot promise that this branch causes no speed regressions. Someone who is better at this might want to check this. To me it seems that it slows down the product of two Permutations(n)
elements by 50% (refining its parent, though), slows down retract_okounkov_vershik
on symmetric group algebra elements by a bit, and speeds up left_action_product
on a symmetric group algebra noticeably.
comment:44 Changed 7 years ago by
 Commit changed from 6657c31932284db43898aee3dc33ca3f5558b544 to 947bed483cd03fbd03cc0741235e50fd8b568193
comment:45 Changed 7 years ago by
I've made some tweaks to the permutations multiplication, which significantly drops the number of function calls according to %prun
, as well as cythonizing it. Here's my timings:
sage: P = Permutations(5) sage: x = P.random_element() sage: y = P.random_element() sage: %timeit x*y 10000 loops, best of 3: 61.2 µs per loop sage: P = Permutations(100) sage: x = P.random_element() sage: y = P.random_element() sage: %timeit x*y 1000 loops, best of 3: 167 µs per loop
Before:
sage: %timeit x*y 10000 loops, best of 3: 87.3 µs per loop sage: %timeit x*y 1000 loops, best of 3: 210 µs per loop
I don't care so much on retract_okounkov_vershik
, but since you say its a very minor regression, I'm not going to consider it (in fact, it might be faster now with faster multiplication). Here's some timings of left_action_product
:
sage: P = Permutations(5) sage: x = P.random_element() sage: Q = Permutations(100) sage: y = Q.random_element() sage: %timeit x*y 1000 loops, best of 3: 300 µs per loop sage: %timeit x.left_action_product(y) 10000 loops, best of 3: 167 µs per loop
Before:
sage: %timeit x*y 1000 loops, best of 3: 225 µs per loop sage: %timeit x.left_action_product(y) 1000 loops, best of 3: 212 µs per loop
So there's ~20% slowdown when multiplying different parents, which surprises me somewhat. Let me see if I can fix that for a few minutes...
comment:46 Changed 7 years ago by
 Commit changed from 947bed483cd03fbd03cc0741235e50fd8b568193 to aebceaf130a0cd513dcd7cfe81b45c2bfc98ba8f
Branch pushed to git repo; I updated commit sha1. New commits:
aebceaf  Speeding up multiplication of different sizes.

comment:47 Changed 7 years ago by
Boom:
sage: P = Permutations(5) sage: x = P.random_element() sage: Q = Permutations(100) sage: y = Q.random_element() sage: %timeit x*y 1000 loops, best of 3: 195 µs per loop
So that should take care of speed regressions (at least any that I care about). So if you're happy with my changes, then let's get this in.
comment:48 Changed 7 years ago by
 Commit changed from aebceaf130a0cd513dcd7cfe81b45c2bfc98ba8f to bcec1c3c2f1dfe0ceff9c51a025b04647246ba5f
Branch pushed to git repo; I updated commit sha1. New commits:
bcec1c3  Doing more wiggling for speed.

comment:49 Changed 7 years ago by
 Commit changed from bcec1c3c2f1dfe0ceff9c51a025b04647246ba5f to b50472eda0f21d983a4bc247ab1fdc8d89d5d0ea
Branch pushed to git repo; I updated commit sha1. New commits:
b50472e  Removing unnecessary code and adding warning.

comment:50 Changed 7 years ago by
 Commit changed from b50472eda0f21d983a4bc247ab1fdc8d89d5d0ea to 011e877182b0d77c4943d34e27173e000e671d58
Branch pushed to git repo; I updated commit sha1. New commits:
a3c0161  16926: added support for WeylGroups, essentially by removing unneeded code + somewhat simplified constructor API + tests

011e877  Merge branch 'public/combinat/fix_sga16926' of trac.sagemath.org:sage into t/16926/public/combinat/fix_sga16926

comment:51 Changed 7 years ago by
Hi,
I have been through the code, and discussed it with Darij and Travis. Please check the above commits; if you are happy with them, this can be positive review, assuming the patchbot goes green.
Thanks Travis and Darij for all the work!
comment:52 Changed 7 years ago by
 Commit changed from 011e877182b0d77c4943d34e27173e000e671d58 to 23cefb9861ae2dc866935bbd6f6b83ff44a36be5
Branch pushed to git repo; I updated commit sha1. New commits:
23cefb9  16926: trivial doctest updates w.r.t. previous merge.

comment:53 Changed 7 years ago by
 Commit changed from 23cefb9861ae2dc866935bbd6f6b83ff44a36be5 to 4c3c9e45fcb8d96a3733229d8b814fe6dd1485d9
Branch pushed to git repo; I updated commit sha1. New commits:
4c3c9e4  I don't think the WeylAlgebra setting is supported enough to be advertised; furthermore the algebra method on nonstandard symmetric groups is fubar

comment:54 Changed 7 years ago by
 Commit changed from 4c3c9e45fcb8d96a3733229d8b814fe6dd1485d9 to 655380d1fb6bd116ae23864b78cde2bf27d7ac24
comment:55 Changed 7 years ago by
 Reviewers set to Darij Grinberg, Nicolas M. Thiéry
 Status changed from needs_review to positive_review
We looked over my latest commits with Travis, and he is fine with them (up to little things we fixed). This is good to go, assuming the patchbot goes green.
New commits:
4c3c9e4  I don't think the WeylAlgebra setting is supported enough to be advertised; furthermore the algebra method on nonstandard symmetric groups is fubar

b2069db  use cythonized left/right_action_products in SGA too

655380d  more optimizations

comment:56 Changed 7 years ago by
 Commit changed from 655380d1fb6bd116ae23864b78cde2bf27d7ac24 to 8fe64bfca71b6a72b4e7837e6ce668e0be2f1128
 Status changed from positive_review to needs_review
comment:57 Changed 7 years ago by
 Commit changed from 8fe64bfca71b6a72b4e7837e6ce668e0be2f1128 to 1f97814d2e67abc00b2f419d2c3836ff54cfe3da
Branch pushed to git repo; I updated commit sha1. New commits:
1f97814  16926: proofread Darij's latest changes

comment:58 Changed 7 years ago by
 Status changed from needs_review to positive_review
I proofread Darij's changes, and implemented the suggestion from his warning; Travis proofread my proofreading. Back to positive review.
comment:59 Changed 7 years ago by
 Commit changed from 1f97814d2e67abc00b2f419d2c3836ff54cfe3da to 12aaaf819bbb30bbd28748f27944d295cd4884d2
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
12aaaf8  doctesting the demise of my bug

comment:60 Changed 7 years ago by
 Keywords days64 added
 Milestone changed from sage6.4 to sage6.6
 Status changed from needs_review to positive_review
LGTM. Darij, are you going to do the (quick) review of #17981?
comment:61 Changed 7 years ago by
Thanks, Travis!
comment:62 Changed 7 years ago by
 Status changed from positive_review to needs_work
Doctest failures
comment:63 Changed 7 years ago by
Could you tell us where you got the failures? (There might also be an issue with us testing this on beta5.)
comment:64 Changed 7 years ago by
The doctests haven't finished yet, but I already get these:
File "src/sage/combinat/backtrack.py", line 867, in sage.combinat.backtrack.TransitiveIdeal Failed example: [p for p in TransitiveIdeal(attrcall("permutohedron_succ"), [Permutation([1,2,3])])] Expected: [[1, 2, 3], [2, 1, 3], [1, 3, 2], [2, 3, 1], [3, 2, 1], [3, 1, 2]] Got: [[1, 2, 3], [2, 1, 3], [1, 3, 2], [2, 3, 1], [3, 1, 2], [3, 2, 1]] ********************************************************************** File "src/sage/combinat/backtrack.py", line 873, in sage.combinat.backtrack.TransitiveIdeal Failed example: [p for p in TransitiveIdeal(attrcall("permutohedron_succ"), [Permutation([3,1,2,4]), Permutation([2,1,3,4])])] Expected: [[2, 1, 3, 4], [2, 1, 4, 3], [2, 4, 1, 3], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 2, 1], [3, 1, 2, 4], [2, 4, 3, 1], [3, 2, 1, 4], [2, 3, 1, 4], [2, 3, 4, 1], [3, 2, 4, 1], [3, 1, 4, 2], [3, 4, 2, 1], [3, 4, 1, 2], [4, 3, 1, 2]] Got: [[2, 1, 3, 4], [3, 1, 2, 4], [2, 1, 4, 3], [3, 1, 4, 2], [2, 3, 1, 4], [3, 4, 1, 2], [3, 4, 2, 1], [2, 3, 4, 1], [2, 4, 1, 3], [3, 2, 1, 4], [4, 3, 1, 2], [4, 3, 2, 1], [3, 2, 4, 1], [4, 2, 1, 3], [2, 4, 3, 1], [4, 2, 3, 1]] ********************************************************************** File "src/sage/combinat/backtrack.py", line 989, in sage.combinat.backtrack.TransitiveIdealGraded Failed example: [p for p in TransitiveIdealGraded(attrcall("permutohedron_succ"), [Permutation([3,1,2,4]), Permutation([2,1,3,4])])] Expected: [[3, 1, 2, 4], [2, 1, 3, 4], [2, 1, 4, 3], [3, 2, 1, 4], [2, 3, 1, 4], [3, 1, 4, 2], [2, 3, 4, 1], [3, 4, 1, 2], [3, 2, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [4, 3, 1, 2], [4, 2, 1, 3], [3, 4, 2, 1], [4, 2, 3, 1], [4, 3, 2, 1]] Got: [[3, 1, 2, 4], [2, 1, 3, 4], [2, 3, 1, 4], [2, 1, 4, 3], [3, 2, 1, 4], [3, 1, 4, 2], [3, 2, 4, 1], [2, 4, 1, 3], [3, 4, 1, 2], [2, 3, 4, 1], [4, 3, 1, 2], [3, 4, 2, 1], [4, 2, 1, 3], [2, 4, 3, 1], [4, 3, 2, 1], [4, 2, 3, 1]] ********************************************************************** 2 items had failures: 2 of 16 in sage.combinat.backtrack.TransitiveIdeal 1 of 8 in sage.combinat.backtrack.TransitiveIdealGraded [176 tests, 3 failures, 102.22 s]
comment:65 Changed 7 years ago by
 Commit changed from 12aaaf819bbb30bbd28748f27944d295cd4884d2 to 009ae6047c1ca8b678cdfd3dcbe96f7159a6fe38
Branch pushed to git repo; I updated commit sha1. New commits:
009ae60  Trivial doctest fixes and removed old note in Groups().

comment:66 Changed 7 years ago by
 Status changed from needs_work to needs_review
Fixed; those which came from the ordering of Permutations
iterator changed because I am now using itertools.permutations
. Also there were some failures in the Groups()
category from an old warning message that I removed. Nicolas and/or Darij, do you agree with my changes?
comment:67 Changed 7 years ago by
I agree. Thank you!
comment:68 Changed 7 years ago by
 Status changed from needs_review to positive_review
I'm taking that as a back to positive_review
.
comment:69 Changed 7 years ago by
 Status changed from positive_review to needs_work
Similarly:
sage t long warnlong 46.4 src/sage/sets/recursively_enumerated_set.pyx ********************************************************************** File "src/sage/sets/recursively_enumerated_set.pyx", line 116, in sage.sets.recursively_enumerated_set Failed example: list(R.elements_of_depth_iterator(9)) Expected: [[5, 4, 2, 3, 1], [4, 5, 3, 2, 1], [5, 3, 4, 2, 1], [5, 4, 3, 1, 2]] Got: [[5, 3, 4, 2, 1], [4, 5, 3, 2, 1], [5, 4, 2, 3, 1], [5, 4, 3, 1, 2]] ********************************************************************** File "src/sage/sets/recursively_enumerated_set.pyx", line 802, in sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet_generic.naive_search_iterator Failed example: list(R.naive_search_iterator()) Expected: [[1, 2, 3], [2, 1, 3], [1, 3, 2], [2, 3, 1], [3, 2, 1], [3, 1, 2]] Got: [[1, 2, 3], [2, 1, 3], [1, 3, 2], [2, 3, 1], [3, 1, 2], [3, 2, 1]] ********************************************************************** 2 items had failures: 1 of 41 in sage.sets.recursively_enumerated_set 1 of 5 in sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet_generic.naive_search_iterator [193 tests, 2 failures, 0.76 s]  sage t long warnlong 46.4 src/sage/sets/recursively_enumerated_set.pyx # 2 doctests failed 
comment:70 Changed 7 years ago by
 Commit changed from 009ae6047c1ca8b678cdfd3dcbe96f7159a6fe38 to bf9fc43cd076381692686dbe26f66a61f7955c1a
Branch pushed to git repo; I updated commit sha1. New commits:
bf9fc43  More order of iteration doctest fixes.

comment:71 Changed 7 years ago by
 Status changed from needs_work to positive_review
Hopefully that's all of them...
comment:72 Changed 7 years ago by
 Status changed from positive_review to needs_info
Hey,
Sorry, before this goes in I'd like to double check with you for which object we changed the enumeration order. I am in the hangout room on the 3rd floor.
Thanks!
Cheers,
comment:73 Changed 7 years ago by
 Status changed from needs_info to positive_review
The change in ordering in these tests was due to the hash changing for the permutations of n
. The hash changed because the parent changed in the sense that it has a much longer MRO due to the change in its category. However the actual iteration of Permutations(n)
has not changed (by lex ordering), so we (Darij, Nicolas, and I) are okay with this.
comment:74 Changed 7 years ago by
 Branch changed from public/combinat/fix_sga16926 to bf9fc43cd076381692686dbe26f66a61f7955c1a
 Resolution set to fixed
 Status changed from positive_review to closed
I don't even know how this is going to happen. AlgebraWithBases?? Coercions back and forth?