#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 tscrim):
Replying to [comment:12 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)`.
See the last part of comment:8.
> > 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 forgot that sarcasm can be lost. Let me be more precise, we don't have
to optimize everything, and it is not like it causes a significant
slowdown. This is on the order of microseconds.
> > 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.
Despite how loaded your phrasing is, you should not be doing `list(p)`
because partitions behave like lists (well, more like tuples). We also
want to make things accessible to the user, and in particular, the
conjugacy classes of permutations are always considered as partitions in
the areas I know. So this makes things nice for the non-programmer-users
who would expect this to be a partition.
Again, having this not return a partition would introduce an inconsistency
with `cycle_type` of `Permutation`.
> > 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.
Then just use the cycle tuples; it doesn't sound like you care about the
ordering.
> > 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].
Ah, sorry; I misread that comment (I thought you said `sorted`).
--
Ticket URL: <http://trac.sagemath.org/ticket/20561#comment:13>
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.
