Clean and enhance module combinat.derangement

[vinklein]

Part of #26883 meta-ticket.

• Replace Derangement's superclass CombinatorialElement with ClonableList.

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

CC: @hivert @sagetrac-boussica

Component: combinatorics

Keywords: thursdaysbdx

Author: Vincent Klein

Branch/Commit: u/vklein/replace_combinatorial_object_to_clonable_list_in_combinat_derangement_derangement @ 650acb7

Reviewer: Adrien Boussicault

Issue created by migration from https://trac.sagemath.org/ticket/26886

[vinklein]

Branch: u/vklein/replace_combinatorial_object_to_clonable_list_in_combinat_derangement_derangement

[vinklein]

Changed keywords from none to thursdaysbdx

[vinklein]

New commits:

9468c54

Trac #26886: Replace CombinatorialObject usage ...

[vinklein]

Commit: 9468c54

[sagetrac-git]

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

092c89f	Trac #26886: Allow to create a Derangement without ...
ade0b9f	Trac #26886: Implement consistency check

[sagetrac-git]

Changed commit from 9468c54 to ade0b9f

[sagetrac-git]

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

b65923b

Trac #26886: Add doctests and documentation.

[sagetrac-git]

Changed commit from ade0b9f to b65923b

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

650acb7

Trac #26886: Add doctests and documentation.

[sagetrac-git]

Changed commit from b65923b to 650acb7

[embray]

comment:10

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 sage-pending or sage-wishlist.

[sagetrac-boussica]

Reviewer: boussica

[sagetrac-boussica]

comment:12

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.

[sagetrac-boussica]

comment:13

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

[vinklein]

Changed reviewer from boussica to Adrien Boussicault

[sagetrac-boussica]

comment:15

Review 1 Remark 2 :

The problem raised by Travis in ticket #26884 comment 12 [#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.

[embray]

comment:17

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[embray]

comment:18

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

[embray]

comment:19

Ticket retargeted after milestone closed

[mkoeppe]

comment:20

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[mkoeppe]

comment:22

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:23

Setting a new milestone for this ticket based on a cursory review.