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: sage-6.6
Component: combinatorics Keywords: days64
Cc: sage-combinat, 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:

Status badges

Description (last modified by tscrim)

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 nthiery

  • Description modified (diff)

comment:2 follow-up: Changed 8 years ago by darij

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

comment:3 in reply to: ↑ 2 Changed 8 years ago by 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(...)).

comment:4 follow-up: Changed 8 years ago by darij

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

comment:6 follow-up: Changed 8 years ago by 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?.

comment:7 in reply to: ↑ 6 Changed 8 years ago by 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.

comment:8 follow-up: Changed 8 years ago by 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).

comment:9 follow-up: Changed 8 years ago by 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.

comment:10 in reply to: ↑ 9 Changed 8 years ago by 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).

comment:11 in reply to: ↑ 8 Changed 8 years ago by 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.

comment:12 Changed 8 years ago by 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 Sn 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 andrew.mathas

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

comment:14 Changed 8 years ago by tscrim

An Abstract Base Class.

comment:15 Changed 7 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Branch set to public/combinat/fix_sga-16926
  • 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 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
    
  1. Refactor the Permutation class to better be an element class, especially parsing of input (hard and tedious).
  1. 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:

8144d47Added optional argument for indexing set of SGA.
a2d9dcdInitial setting of StandardPermutations_n to be in FiniteWeylGroups.
765cbdbFixes and tweaks and speedups.
a63dfd3Added support for conjugacy classes for permutation groups.
f15f40cSome additional fixes and cleanup.

comment:16 follow-up: Changed 7 years ago by 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?

Last edited 7 years ago by darij (previous) (diff)

comment:17 Changed 7 years ago by git

  • Commit changed from f15f40cd95cd94cd3e4a3b843fd0b257746d43f0 to 6597e7936048b8f30018a5e4a6e566836f6e5e68

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

8e98447Merge branch 'public/combinat/fix_sga-16926' of trac.sagemath.org:sage into public/combinat/fix_sga-16926
6597e79Change Darij requested plus fixed a trivial doctest.

comment:18 in reply to: ↑ 16 Changed 7 years ago by 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.

comment:19 Changed 7 years ago by 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).

comment:20 Changed 7 years ago by 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.

comment:21 Changed 7 years ago by git

  • Commit changed from 6597e7936048b8f30018a5e4a6e566836f6e5e68 to 18b3441e41e0f30b6bc02bd5a746096b17189e27

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

18b3441Using itertools and moved methods from n_abstract.

comment:22 Changed 7 years ago by 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

comment:23 follow-up: Changed 7 years ago by 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?

comment:24 in reply to: ↑ 23 Changed 7 years ago by 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).

comment:25 Changed 7 years ago by git

  • Commit changed from 18b3441e41e0f30b6bc02bd5a746096b17189e27 to f1202558f449a7797c86143a59e5c3e32a5349d8

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

2b3a48fMerge branch 'public/combinat/fix_sga-16926' of git://trac.sagemath.org/sage into sga
f120255allow circumventing mult variable in has_left/right_descent methods

comment:26 Changed 7 years ago by 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?

comment:27 Changed 7 years ago by tscrim

Yes, it works for me.

comment:28 Changed 7 years ago by git

  • Commit changed from f1202558f449a7797c86143a59e5c3e32a5349d8 to caf4f43a19035e37cb4b4c67f0f040af84783c9e

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

caf4f43some more edits

comment:29 Changed 7 years ago by 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.

comment:30 Changed 7 years ago by git

  • Commit changed from caf4f43a19035e37cb4b4c67f0f040af84783c9e to f38fe13587fac895809d5f9d5fcf21b12bd23f0a

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

f38fe13I 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 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().
Last edited 7 years ago by darij (previous) (diff)

comment:32 Changed 7 years ago by tscrim

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

  • Commit changed from f38fe13587fac895809d5f9d5fcf21b12bd23f0a to d4568f6e72f40500e1a39d56b4a4f74146fcab29

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

cd15df4Merge branch 'develop' into public/combinat/fix_sga-16926
d01b36dMerge branch 'develop' into public/combinat/fix_sga-16926
0c95381Merge branch 'develop' into public/combinat/fix_sga-16926
cb7e154Some fixing of the index_set options.
c9ebdd7Implement coerce map for Permutations(n).
b0973dcFix coercion map when _coerce_map_from_ returns a callable.
bd0fcd1Merge branch 'public/coerce/fix_coerce_map_from_callable' into public/combinat/fix_sga-16926
d4568f6Finish implementing coercion maps from SymmetricGroup to Permutations(n).

comment:34 Changed 7 years ago by git

  • Commit changed from d4568f6e72f40500e1a39d56b4a4f74146fcab29 to 9666765a5d7cbab9bfb2b284017fc15be0ab1518

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

9666765Allowing methods to work for other indexing sets.

comment:35 Changed 7 years ago by 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.

comment:36 follow-up: Changed 7 years ago by virmaux

Should not algebra_generators return a Family instead of a list ?

comment:37 Changed 7 years ago by git

  • Commit changed from 9666765a5d7cbab9bfb2b284017fc15be0ab1518 to 7daaa83ee93aace69ce63e3ad80d1c5e43f5cdd7

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

7daaa83Made algebra_generators return a Family.

comment:38 in reply to: ↑ 36 Changed 7 years ago by 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.

comment:39 Changed 7 years ago by git

  • Commit changed from 7daaa83ee93aace69ce63e3ad80d1c5e43f5cdd7 to f11ba248bd9cf4e88949cb628fa38063b04c0787

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

f11ba24further corrections in SymmetricGroupAlgebra

comment:40 Changed 7 years ago by git

  • Commit changed from f11ba248bd9cf4e88949cb628fa38063b04c0787 to de5eb2ffa58726499d0c2a6a396d1bdcc9fedfbc

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

de5eb2fmore fixes & warnings

comment:41 Changed 7 years ago by git

  • Commit changed from de5eb2ffa58726499d0c2a6a396d1bdcc9fedfbc to d097fdf6dc78cf7c1bc97781062bd22418f8d8ef

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

d097fdfreview complete(?):

comment:42 Changed 7 years ago by git

  • Commit changed from d097fdf6dc78cf7c1bc97781062bd22418f8d8ef to 6657c31932284db43898aee3dc33ca3f5558b544

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

6657c31what subsets?

comment:43 Changed 7 years ago by 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.

comment:44 Changed 7 years ago by git

  • Commit changed from 6657c31932284db43898aee3dc33ca3f5558b544 to 947bed483cd03fbd03cc0741235e50fd8b568193

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

662421dCythonized permutation multiplication and trying to remove speed regression.
947bed4Merge branch 'public/combinat/fix_sga-16926' of trac.sagemath.org:sage into public/combinat/fix_sga-16926

comment:45 Changed 7 years ago by 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...

comment:46 Changed 7 years ago by git

  • Commit changed from 947bed483cd03fbd03cc0741235e50fd8b568193 to aebceaf130a0cd513dcd7cfe81b45c2bfc98ba8f

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

aebceafSpeeding up multiplication of different sizes.

comment:47 Changed 7 years ago by 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.

Last edited 7 years ago by tscrim (previous) (diff)

comment:48 Changed 7 years ago by git

  • Commit changed from aebceaf130a0cd513dcd7cfe81b45c2bfc98ba8f to bcec1c3c2f1dfe0ceff9c51a025b04647246ba5f

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

bcec1c3Doing more wiggling for speed.

comment:49 Changed 7 years ago by git

  • Commit changed from bcec1c3c2f1dfe0ceff9c51a025b04647246ba5f to b50472eda0f21d983a4bc247ab1fdc8d89d5d0ea

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

b50472eRemoving unnecessary code and adding warning.

comment:50 Changed 7 years ago by git

  • Commit changed from b50472eda0f21d983a4bc247ab1fdc8d89d5d0ea to 011e877182b0d77c4943d34e27173e000e671d58

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

a3c016116926: added support for WeylGroups, essentially by removing unneeded code + somewhat simplified constructor API + tests
011e877Merge branch 'public/combinat/fix_sga-16926' of trac.sagemath.org:sage into t/16926/public/combinat/fix_sga-16926

comment:51 Changed 7 years ago by 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!

Last edited 7 years ago by nthiery (previous) (diff)

comment:52 Changed 7 years ago by git

  • Commit changed from 011e877182b0d77c4943d34e27173e000e671d58 to 23cefb9861ae2dc866935bbd6f6b83ff44a36be5

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

23cefb916926: trivial doctest updates w.r.t. previous merge.

comment:53 Changed 7 years ago by git

  • Commit changed from 23cefb9861ae2dc866935bbd6f6b83ff44a36be5 to 4c3c9e45fcb8d96a3733229d8b814fe6dd1485d9

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

4c3c9e4I 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 git

  • Commit changed from 4c3c9e45fcb8d96a3733229d8b814fe6dd1485d9 to 655380d1fb6bd116ae23864b78cde2bf27d7ac24

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

b2069dbuse cythonized left/right_action_products in SGA too
655380dmore optimizations

comment:55 Changed 7 years ago by nthiery

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

4c3c9e4I don't think the WeylAlgebra setting is supported enough to be advertised; furthermore the algebra method on nonstandard symmetric groups is fubar
b2069dbuse cythonized left/right_action_products in SGA too
655380dmore optimizations

comment:56 Changed 7 years ago by git

  • Commit changed from 655380d1fb6bd116ae23864b78cde2bf27d7ac24 to 8fe64bfca71b6a72b4e7837e6ce668e0be2f1128
  • 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:

49307d716926: proofreading with Travis
8fe64bfMerge branch 'public/combinat/fix_sga-16926' of trac.sagemath.org:sage into t/16926/public/combinat/fix_sga-16926

comment:57 Changed 7 years ago by git

  • Commit changed from 8fe64bfca71b6a72b4e7837e6ce668e0be2f1128 to 1f97814d2e67abc00b2f419d2c3836ff54cfe3da

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

1f9781416926: proofread Darij's latest changes

comment:58 Changed 7 years ago by nthiery

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

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

12aaaf8doctesting the demise of my bug

comment:60 Changed 7 years ago by tscrim

  • Keywords days64 added
  • Milestone changed from sage-6.4 to sage-6.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 darij

Thanks, Travis!

comment:62 Changed 7 years ago by vbraun

  • Status changed from positive_review to needs_work

Doctest failures

comment:63 Changed 7 years ago by tscrim

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

Last edited 7 years ago by tscrim (previous) (diff)

comment:64 Changed 7 years ago by 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]

comment:65 Changed 7 years ago by git

  • Commit changed from 12aaaf819bbb30bbd28748f27944d295cd4884d2 to 009ae6047c1ca8b678cdfd3dcbe96f7159a6fe38

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

009ae60Trivial doctest fixes and removed old note in Groups().

comment:66 Changed 7 years ago by tscrim

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

Last edited 7 years ago by tscrim (previous) (diff)

comment:67 Changed 7 years ago by darij

I agree. Thank you!

comment:68 Changed 7 years ago by tscrim

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

  • Status changed from positive_review to needs_work

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

comment:70 Changed 7 years ago by git

  • Commit changed from 009ae6047c1ca8b678cdfd3dcbe96f7159a6fe38 to bf9fc43cd076381692686dbe26f66a61f7955c1a

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

bf9fc43More order of iteration doctest fixes.

comment:71 Changed 7 years ago by tscrim

  • Status changed from needs_work to positive_review

Hopefully that's all of them...

comment:72 Changed 7 years ago by nthiery

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

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

  • Branch changed from public/combinat/fix_sga-16926 to bf9fc43cd076381692686dbe26f66a61f7955c1a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.