#20561: Return cycle type of a permutation
-------------------------------------+-------------------------------------
Reporter: andrew.mathas | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-7.2
Component: group theory | Resolution:
Keywords: permutation, | Merged in:
cycle type | Reviewers:
Authors: Andrew Mathas | Work issues:
Report Upstream: N/A | Commit:
Branch: | b9acb7729e678ee46ef6db66a694c3040db830d0
u/andrew.mathas/return_cycle_type_of_a_permutation| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by vdelecroix):
Replying to [comment:11 tscrim]:
> I get much less percentage of time to construct a partition:
Your code is not the same as mine since you ignore the creation of the
parent. In Andrew's code the call is precisely `Partition(ls)`. You should
time the call `P = Partitions(); p = P(ls)`.
> Besides, not everything has to be ultra-super-optimized (plus these
operations are not being compared fairly since the `Partition` call is
Python). In this case, the consistency is much more desirable.
(Technically to be fair, you need to include the singletons, but I believe
these are "rare".) Averaging over all partitions and using `%lprun`, I get
that it takes ~80% of the time.
A 80% gain is not what I would call super-optimization.
> I would say what would need to be done is improve the creation time of
partitions if this is an issue for you Vincent.
Creating a partition from a tuple is trivial at no extra cost: just do
`Partition(l)`. On the other hand, creating a list from a partition is:
`list(p)` and this costs a >80% slow down.
> Also, I don't know how it would make sense to disregard singletons. They
are needed because the cycle types (with cycle types) determine the
conjugacy classes of the symmetric group.
It makes sense in a lot of situations. Especially when you count solutions
of equations in the symmetric group. Getting the conjugacy is not the only
important thing.
> Side note: if you really care about speed, you should use
`list.sort(reverse=True)` because it does it in place and does not create
a second list.
This is precisely what is done in Andrew's code and that I asked for in
[comment:5].
--
Ticket URL: <http://trac.sagemath.org/ticket/20561#comment:12>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
