Clean and enhance module combinat.derangement

[vklein]

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]
  

[vklein]

New commits:

​9468c54

Trac #26886: Replace CombinatorialObject usage ...

[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

[git]

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

​b65923b

Trac #26886: Add doctests and documentation.

[git]

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

​650acb7

Trac #26886: Add doctests and documentation.

[embray]

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.

[boussica]

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.

[boussica]

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

[boussica]

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.

[embray]

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

[embray]

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