Opened 12 months ago
Last modified 6 months ago
#26886 needs_work enhancement
Clean and enhance module combinat.derangement
Reported by:  vklein  Owned by:  

Priority:  major  Milestone:  sage8.9 
Component:  combinatorics  Keywords:  thursdaysbdx 
Cc:  hivert, boussica  Merged in:  
Authors:  Vincent Klein  Reviewers:  Adrien Boussicault 
Report Upstream:  N/A  Work issues:  
Branch:  u/vklein/replace_combinatorial_object_to_clonable_list_in_combinat_derangement_derangement (Commits)  Commit:  650acb7c198ff9fa5fc6e6cb7d0773863015491e 
Dependencies:  Stopgaps: 
Description (last modified by )
Part of #26883 metaticket.
 Replace
Derangement
's superclassCombinatorialElement
withClonableList
.
 Allow to create a Derangement without declaring it's parent explicitly. The parent set generated is the list [1, 2, ..., n] where n is the length of the Derangement.
sage: d=Derangement([2,3,1]) sage: d.parent() Derangements of the set [1, 2, 3]
 Implement consistency check when creating a
Derangement
. There is no control currently and inconsistencies are easy to build:sage: D = Derangements(4) sage: elt=D([1,2,3,4]) sage: tuple(elt) == D._set True sage: D([12,87,4,5]).parent() Derangements of the set [1, 2, 3, 4] sage: D([2,1]).parent() Derangements of the set [1, 2, 3, 4]
Change History (18)
comment:1 Changed 12 months ago by
 Branch set to u/vklein/replace_combinatorial_object_to_clonable_list_in_combinat_derangement_derangement
comment:2 Changed 12 months ago by
 Commit set to 9468c54ab54ad95d6650e1bd6a68a8f561ec3b07
 Keywords thursdaysbdx added
comment:3 Changed 12 months ago by
 Description modified (diff)
 Summary changed from Replace Combinatorial Object to Clonable List in combinat.derangement.Derangement to Replace Combinatorial Element to Clonable List in combinat.derangement.Derangement
comment:4 Changed 12 months ago by
 Summary changed from Replace Combinatorial Element to Clonable List in combinat.derangement.Derangement to Clean and enhance module combinat.derangement
comment:5 Changed 12 months ago by
 Commit changed from 9468c54ab54ad95d6650e1bd6a68a8f561ec3b07 to ade0b9fd1717993312cc548e24beb8097472ea25
comment:6 Changed 12 months ago by
 Commit changed from ade0b9fd1717993312cc548e24beb8097472ea25 to b65923b05087906b8fc35e469605f28858db31cb
Branch pushed to git repo; I updated commit sha1. New commits:
b65923b  Trac #26886: Add doctests and documentation.

comment:7 Changed 12 months ago by
 Cc hivert boussica added
 Status changed from new to needs_review
comment:8 Changed 12 months ago by
 Commit changed from b65923b05087906b8fc35e469605f28858db31cb to 650acb7c198ff9fa5fc6e6cb7d0773863015491e
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
650acb7  Trac #26886: Add doctests and documentation.

comment:9 Changed 11 months ago by
 Milestone changed from sage8.5 to sage8.6
comment:10 Changed 11 months ago by
 Milestone changed from sage8.6 to sage8.7
Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sagepending or sagewishlist.
comment:11 Changed 10 months ago by
 Reviewers set to boussica
comment:12 Changed 10 months ago by
Review 1 remark 1
In __classccall_private__()
, i think that you modify the functionalities of the Derangements class.
In their documentation, a derangement on a set S is a permutation sigma such that
sigma(x) neq x for all x in S, i.e. sigma is a permutation of S with no fixed points.
So S can be an arbitrary set. For example, S can be equals to [1,x,x**2]
. The following code shows that functionality:
sage: DDS = Derangements([1, x, x^2]) sage: DDS Derangements of the set [x, x + 1, x^2] sage: list( DDS ) [[x + 1, x^2, x], [x^2, x, x + 1]]
So, in the code of __class_call__private__()
you should'nt write
+ parent_set = [i + 1 for i in range(len(lst))] + return Derangements(parent_set)(lst)
Indeed, you tranform any Derangment on any set to a derangement on some integers.
See the next comment for more details.
comment:13 followup: ↓ 15 Changed 10 months ago by
Review 1 remark 1 bis
The problem is the following : "how do we define correctly, without the parent, a derangement ?"
For example with your code we have :
sage: Derangement([2,3,1]) [2, 3, 1]
and
sage: Derangement([x**3, 1+x, x**2])  AssertionError ... AssertionError: All elements of a derangement must be present in their parent set
The problem is : the constructor should deduce the parent with just a list of elements. It is not possible since a bijection is : a support (often implemented with a list of elements) and the image of the support (implemented by another list of the same elements).
So, we need those two informations.
So i propose the following solutions :
1) we remove the constructor class_call_private and say that user have to use the parents to
construct their objects
2) we improve the message error :
"Impossible to guess parents, please construct your derangement by using Derangements"
3) we check if the elements of the list have a canonical total order, we order them and construct
the parent Derangements( sorted(lst) )
4) The constructor of derangement should always have a list of elements and an order function in parameter. During the construction a parent is obtained with the ordering function and then, the derangement is obtained with the help of the parent. If the ordering function is None, the constructor will use the default ordering on the element.
In my opinion, i prefer the solution 4).
comment:14 Changed 10 months ago by
 Reviewers changed from boussica to Adrien Boussicault
comment:15 in reply to: ↑ 13 Changed 10 months ago by
Review 1 Remark 2 :
The problem raised by Travis in ticket #26884 comment 12 https://trac.sagemath.org/ticket/26884#comment:12 can be applyed to this ticket.
Travis worte :
1 on going through an essentially trivial _element_constructor_ in internal code that should give valid > output. At the very least, you should not run the checks when constructing objects from internal code.
We need to fix and discuss the functionality of ClonableList
class , Check()
function and thet SetFactory
framework with Florent to answer correctly to that question.
comment:16 Changed 10 months ago by
 Status changed from needs_review to needs_work
comment:17 Changed 9 months ago by
 Milestone changed from sage8.7 to sage8.8
Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)
comment:18 Changed 6 months ago by
 Milestone changed from sage8.8 to sage8.9
Tickets still needing working or clarification should be moved to the next release milestone at the soonest (please feel free to revert if you think the ticket is close to being resolved).
New commits:
Trac #26886: Replace CombinatorialObject usage ...