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: sage-8.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 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]
    

Change History (18)

comment:1 Changed 12 months ago by vklein

  • Branch set to u/vklein/replace_combinatorial_object_to_clonable_list_in_combinat_derangement_derangement

comment:2 Changed 12 months ago by vklein

  • Commit set to 9468c54ab54ad95d6650e1bd6a68a8f561ec3b07
  • Keywords thursdaysbdx added

New commits:

9468c54Trac #26886: Replace CombinatorialObject usage ...

comment:3 Changed 12 months ago by vklein

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

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

  • Commit changed from 9468c54ab54ad95d6650e1bd6a68a8f561ec3b07 to ade0b9fd1717993312cc548e24beb8097472ea25

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

092c89fTrac #26886: Allow to create a Derangement without ...
ade0b9fTrac #26886: Implement consistency check

comment:6 Changed 12 months ago by git

  • Commit changed from ade0b9fd1717993312cc548e24beb8097472ea25 to b65923b05087906b8fc35e469605f28858db31cb

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

b65923bTrac #26886: Add doctests and documentation.

comment:7 Changed 12 months ago by vklein

  • Cc hivert boussica added
  • Status changed from new to needs_review

comment:8 Changed 12 months ago by git

  • Commit changed from b65923b05087906b8fc35e469605f28858db31cb to 650acb7c198ff9fa5fc6e6cb7d0773863015491e

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

650acb7Trac #26886: Add doctests and documentation.

comment:9 Changed 11 months ago by vklein

  • Milestone changed from sage-8.5 to sage-8.6

comment:10 Changed 11 months ago by embray

  • Milestone changed from sage-8.6 to sage-8.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 sage-pending or sage-wishlist.

comment:11 Changed 10 months ago by boussica

  • Reviewers set to boussica

comment:12 Changed 10 months ago by 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.

Last edited 10 months ago by boussica (previous) (diff)

comment:13 follow-up: Changed 10 months ago by 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).

Last edited 10 months ago by boussica (previous) (diff)

comment:14 Changed 10 months ago by vklein

  • Reviewers changed from boussica to Adrien Boussicault

comment:15 in reply to: ↑ 13 Changed 10 months ago by 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.

comment:16 Changed 10 months ago by boussica

  • Status changed from needs_review to needs_work

comment:17 Changed 9 months ago by embray

  • Milestone changed from sage-8.7 to sage-8.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 embray

  • Milestone changed from sage-8.8 to sage-8.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).

Note: See TracTickets for help on using tickets.