Merge the features of SymmetricGroupAlgebra and SymmetricGroup.algebra

[nthiery]

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.

[darij]

I don't even know how this is going to happen. AlgebraWithBases?? Coercions back and forth?

[nthiery]

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(...)).

[darij]

Isn't that harder? There'd be quite a lot of functionality to triplicate...

[nthiery]

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.

[darij]

Oh, you want to move things like the Young-Jucys-Murphy 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?.

[nthiery]

Replying to darij:

Oh, you want to move things like the Young-Jucys-Murphy 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.

[tscrim]

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).

[darij]

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.

[tscrim]

Replying to darij:

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.

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).

[nthiery]

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.

[tscrim]

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.

[andrew.mathas]

Silly question, no doubt, but what is an ABC?

[tscrim]

An Abstract Base Class.

[tscrim]

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 that TestSuite passes.

• I've added as much common functionality between SymmetricGroup and Permutations since the former is a gap version of the latter. I'm leaving WeylGroup 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 micro-optimizations.

• 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:

1. 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
   

2. Refactor the Permutation class to better be an element class, especially parsing of input (hard and tedious).

3. 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 (Yucis-Murphy elements, ...) from SymmetricGroupAlgebra to the category SymmetricGroups.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.

[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.

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 order-of-multiplication 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?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​8e98447	Merge branch 'public/combinat/fix_sga-16926' of trac.sagemath.org:sage into public/combinat/fix_sga-16926
​6597e79	Change Darij requested plus fixed a trivial doctest.

[tscrim]

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 order-of-multiplication 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?

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.

[virmaux]

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).

[darij]

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.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​18b3441

Using itertools and moved methods from n_abstract.

[tscrim]

__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

[darij]

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?

[tscrim]

Replying to darij:

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?

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).

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2b3a48f	Merge branch 'public/combinat/fix_sga-16926' of git://trac.sagemath.org/sage into sga
​f120255	allow circumventing mult variable in has_left/right_descent methods

[darij]

Ah, if it was already semi-broken 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?

[tscrim]

Yes, it works for me.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​caf4f43

some more edits

[darij]

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.

[git]

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

[darij]

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) to SymmetricGroupAlgebra(QQ, 3), but applying this coercion to elements fails. This is because StandardPermutations_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 duck-typing in that constructor.

• Various methods don't work for SymmetricGroup(3).algebra(QQ), and the fix is not as simple as adding index_set=self.basis().keys().

[tscrim]

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.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​cd15df4	Merge branch 'develop' into public/combinat/fix_sga-16926
​d01b36d	Merge branch 'develop' into public/combinat/fix_sga-16926
​0c95381	Merge branch 'develop' into public/combinat/fix_sga-16926
​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_sga-16926
​d4568f6	Finish implementing coercion maps from SymmetricGroup to Permutations(n).

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9666765

Allowing methods to work for other indexing sets.

[tscrim]

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.

[virmaux]

Should not algebra_generators return a Family instead of a list ?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​7daaa83

Made algebra_generators return a Family.

[tscrim]

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.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f11ba24

further corrections in SymmetricGroupAlgebra

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​de5eb2f

more fixes & warnings

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d097fdf

review complete(?):

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​6657c31

what subsets?

[darij]

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.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​662421d	Cythonized permutation multiplication and trying to remove speed regression.
​947bed4	Merge branch 'public/combinat/fix_sga-16926' of trac.sagemath.org:sage into public/combinat/fix_sga-16926

[tscrim]

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...

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​aebceaf

Speeding up multiplication of different sizes.

[tscrim]

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.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​bcec1c3

Doing more wiggling for speed.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b50472e

Removing unnecessary code and adding warning.

[git]

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_sga-16926' of trac.sagemath.org:sage into t/16926/public/combinat/fix_sga-16926

[nthiery]

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!

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​23cefb9

16926: trivial doctest updates w.r.t. previous merge.

[git]

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

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b2069db	use cythonized left/right_action_products in SGA too
​655380d	more optimizations

[nthiery]

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

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​49307d7	16926: proofreading with Travis
​8fe64bf	Merge branch 'public/combinat/fix_sga-16926' of trac.sagemath.org:sage into t/16926/public/combinat/fix_sga-16926

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​1f97814

16926: proofread Darij's latest changes

[nthiery]

I proofread Darij's changes, and implemented the suggestion from his warning; Travis proofread my proofreading. Back to positive review.

[git]

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

[tscrim]

LGTM. Darij, are you going to do the (quick) review of #17981?

[darij]

Thanks, Travis!

[vbraun]

Doctest failures

[tscrim]

Could you tell us where you got the failures? (There might also be an issue with us testing this on beta5.)

[jkeitel]

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]

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​009ae60

Trivial doctest fixes and removed old note in Groups().

[tscrim]

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?

[darij]

I agree. Thank you!

[tscrim]

I'm taking that as a back to positive_review.

[jhpalmieri]

Similarly:

sage -t --long --warn-long 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 --warn-long 46.4 src/sage/sets/recursively_enumerated_set.pyx  # 2 doctests failed
----------------------------------------------------------------------

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​bf9fc43

More order of iteration doctest fixes.

[tscrim]

Hopefully that's all of them...

[nthiery]

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,

[tscrim]

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.