#18347 closed enhancement (fixed)
implement the shard intersection order on permutations
Reported by:  chapoton  Owned by:  

Priority:  minor  Milestone:  sage6.8 
Component:  combinatorics  Keywords:  poset 
Cc:  darij, tscrim, hthomas  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  854de65 (Commits)  Commit:  
Dependencies:  Stopgaps: 
Description
This is a poset (and even a lattice) introduced by N. Reading in 2011.
It has nice properties, similar to that of noncrossing partitions.
Let's have it in sage.
Change History (33)
comment:1 Changed 6 years ago by
 Branch set to u/chapoton/18347
 Cc darij tscrim hthomas added
 Commit set to 5d0cf22c73b983f3b59d2dd154205d78f0a2e7c8
 Keywords poset added
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
You might have forgotten to gitadd the main file?
comment:3 Changed 6 years ago by
 Commit changed from 5d0cf22c73b983f3b59d2dd154205d78f0a2e7c8 to c8d90002fe00c2ace0fa56abd7b035974645ed38
Branch pushed to git repo; I updated commit sha1. New commits:
c8d9000  trac #18347 main file was forgotten

comment:4 Changed 6 years ago by
oops, indeed, I was a bit too quick
Do you think that descending_runs should be integrated into runs ?
comment:5 Changed 6 years ago by
I don't know  this seems to be a matter of taste.
comment:6 Changed 6 years ago by
 Status changed from needs_review to needs_work
Hello,
 In
decreasing_runs
why are you creating a list to return a tuple? You would better usereturn tuple(tuple([n + 1  i for i in r]) for r in s_bar.runs())
 What is the point of the
cached_function
onshard_preorder_graph
? As far as I understand the information is only temporarily used to construct the poset. The poset constructor basically makes comparison between all pairs. So you are storing information that will never be used beyond constructing the poset.
 proposition 1: implement better the data to initialize the poset from
 (ugly) proposition 2: clear the cache when you are done
Sn = [s.decreasing_runs() for s in Permutations(n)] P = Poset([Sn, shard_compares], cover_relations=False) shard_preorder_graph.clear_cache() return P
 This
dico1 = {} # conversion: integer > index of run in r1 for i, bloc in enumerate(r1): for j in bloc: dico1[j] = i
can bedico1 = {j:i for i,bloc in enumerate(r1) for j in bloc}
Vincent
comment:7 Changed 6 years ago by
 Commit changed from c8d90002fe00c2ace0fa56abd7b035974645ed38 to e32ecc3a9702cc7ab69ba180eb75f02623418186
Branch pushed to git repo; I updated commit sha1. New commits:
e32ecc3  trac #18347 some of the reviewer's minor comments

comment:8 followup: ↓ 9 Changed 6 years ago by
Thanks for the comments. I have corrected the two minor ones.
About the caching: indeed, this is used only in the poset, but used many times.
It is not clear to me how to avoid that. One could precompute in the poset method all
these digraphs, and keep them in a list or a dictionary, and make the shard_compares
method an internal one. I am not convinced that this would make things more clear.
comment:9 in reply to: ↑ 8 ; followup: ↓ 10 Changed 6 years ago by
Replying to chapoton:
Thanks for the comments. I have corrected the two minor ones.
About the caching: indeed, this is used only in the poset, but used many times.
It is currently not used in the poset, only during its construction! Just have a look at the ugly poset code. It is not lazy at all.
runs
anddecreasing_runs
should return the same data. It is currently list for one of them and tuple for the other.
 Why did you wrote the following comment in
shard_compares
?# We assume that r1 has less runs than r0
 The function
shard_preorder_graph
only depends on the interval not on the runs themselves. So you are storing too much in the cache of this function. Make the input a tuple of pairssage: s = Permutation([2,8,3,9,6,4,5,1,7]) sage: runs = s.decreasing_runs() sage: shard_preorder_graph(runs) == \ ....: shard_preorder_graph(tuple((r[0],r[1]) for r in runs)) True
And you should really think moving it somewhere else as this has nothing to do with permutations. This is just a comparability graph given by the inclusion order on intervals. Isn't it?
Vincent
comment:10 in reply to: ↑ 9 Changed 6 years ago by
Replying to vdelecroix:
Replying to chapoton:
And you should really think moving it somewhere else as this has nothing to do with permutations. This is just a comparability graph given by the inclusion order on intervals. Isn't it?
This is not quite true, sorry. You are building a comparability graph that also does depend on the order of the input. Not only on the intervals themselves...
Vincent
comment:11 Changed 6 years ago by
 Commit changed from e32ecc3a9702cc7ab69ba180eb75f02623418186 to 88b08d58b257dbaa72ab98f027cc5023d7224a2a
Branch pushed to git repo; I updated commit sha1. New commits:
88b08d5  trac #18347 more reviewer comments, still not the main one

comment:12 followup: ↓ 13 Changed 6 years ago by
Hello,
yes, this is a rather subtle order, I think. It is indeed closely related to noncrossing partitions and to the weak order, but not in obvious ways. For example, the Mobius number is the number of connected partitions.
Concerning 4: I have added an option to specify the output of decreasing runs. Should I do the same for runs ?
Concerning 5: I have added this as a simple necessary condition
concerning 6: I have made shard_preorder_graph
input a tuple of pairs
comment:13 in reply to: ↑ 12 Changed 6 years ago by
Why not making it a poset on permutations?
Replying to chapoton:
Hello,
yes, this is a rather subtle order, I think. It is indeed closely related to noncrossing partitions and to the weak order, but not in obvious ways. For example, the Mobius number is the number of connected partitions.
Concerning 4: I have added an option to specify the output of decreasing runs. Should I do the same for runs ?
I think so.
Concerning 5: I have added this as a simple necessary condition
concerning 6: I have made
shard_preorder_graph
input a tuple of pairs
Nice.
I uploaded a branch at public/18347
in which instead of storing every graph in an external function I created a new class for ShardPosetElement
. It does some precomputation. It is much cleaner. It is just a toy implementation to let you see. Your previous shard_compares
is now ShardPosetElement.__le__
.
Beyond these technicalities:
 you must put more definitions (about the order, etc)
 you should put more relevant doctest!
sage: P = posets.ShardPoset(4); P Finite poset containing 24 elements sage: len(P.maximal_chains()) 34 sage: P.is_selfdual() False
is clearly not enough!
Vincent
comment:14 Changed 6 years ago by
 Commit changed from 88b08d58b257dbaa72ab98f027cc5023d7224a2a to 70cf5e89ef4898cc519204e55fbcdfe797215894
comment:15 Changed 6 years ago by
 Commit changed from 70cf5e89ef4898cc519204e55fbcdfe797215894 to db7c51a51a7e37d39a5ee015772d5cdc3e254e2d
Branch pushed to git repo; I updated commit sha1. New commits:
db7c51a  trac #18347 more explanations in the doc

comment:16 Changed 6 years ago by
 Status changed from needs_work to needs_review
I have added some explanations. Enough ?
comment:17 followup: ↓ 19 Changed 6 years ago by
 Status changed from needs_review to needs_work
Hello,
What does connected_parts
is doing in the git branch?
You should work harder on ShardPosetElement
:
 it would be better if it inherits from
tuple
(i.e. remove thep
attribute and addtuple.__init__(self, p)
in the constructor). Then remove the__hash__
and the__repr__
(they are already fine intuple
)
 Implement the various operators
__le__
,__lt__
,__gt__
,__ge__
and check that it is coherent (this should be ok for__eq__
and__ne__
inherited fromtuple
)
 Moreover, in
__le__
you can not assume thatself
andother
are of the same type. You should start the method with something like:if type(self) is not type(other) or len(self) != len(other): raise TypeError("these are not comparable")
 Do you want to keep all attributes of
ShardPosetElement
public as they are?
Vincent
comment:18 Changed 6 years ago by
 Commit changed from db7c51a51a7e37d39a5ee015772d5cdc3e254e2d to 878ed3a0794d123c46d7cb9ea48ad93ca2d07348
comment:19 in reply to: ↑ 17 ; followup: ↓ 20 Changed 6 years ago by
Hello
What does
connected_parts
is doing in the git branch?
Well, I removed it. Could go in another ticket maybe.
 it would be better if it inherits from
tuple
(i.e. remove thep
attribute and addtuple.__init__(self, p)
in the constructor). Then remove the__hash__
and the__repr__
(they are already fine intuple
)
Done
 Implement the various operators
__le__
,__lt__
,__gt__
,__ge__
and check that it is coherent (this should be ok for__eq__
and__ne__
inherited fromtuple
)
Is this really necessary ? This class is just there to help build the poset, there is no way it will be ever used for something else, I think.
 Moreover, in
__le__
you can not assume thatself
andother
are of the same type. You should start the method with something like:if type(self) is not type(other) or len(self) != len(other): raise TypeError("these are not comparable")
Done
 Do you want to keep all attributes of
ShardPosetElement
public as they are?
Once again, this class will probably not be very much used. So I do not see the point to hide things.
My motivation for this ticket was to have the poset, which is the main interesting thing here.
Thanks for your comments, by the way.
Frederic
comment:20 in reply to: ↑ 19 Changed 6 years ago by
Hi,
Replying to chapoton:
I mostly agree with you for 2. and 4. But if you do not care about the elements, then the poset should be abstract on integers: i.e. just store a matrix of relations and send it to Poset
. You do not want to know which permutation corresponds to which point in this poset?
Vincent
comment:21 followup: ↓ 22 Changed 6 years ago by
Well. I did implement this just to compute the number of maximal chains and the mobius numbers. So only the "abstract" poset was needed. But of course, this is more useful to other people if the vertices of the poset are more or less labelled by permutations.
I do not think nevertheless that it is necessary to have the elements be permutations.
So I am happy with the current state of things..
comment:22 in reply to: ↑ 21 Changed 6 years ago by
Replying to chapoton:
Well. I did implement this just to compute the number of maximal chains and the mobius numbers. So only the "abstract" poset was needed. But of course, this is more useful to other people if the vertices of the poset are more or less labelled by permutations.
I do not think nevertheless that it is necessary to have the elements be permutations.
So I am happy with the current state of things..
I see. Could you mention somewhere (probably in the docstring of ShardPosetElement
and ShardPoset
) that the elements are not permutation (for computational reasons). But hopefully they are easily recovered:
sage: P = posets.ShardPoset(4) sage: mins = P.minimal_elements()[0] sage: p = Permutation(mins) [2, 3, 4, 1] sage: p.decreasing_runs() [[2], [3], [4, 1]]
(or a more relevant example)
Vincent
comment:23 Changed 6 years ago by
 Commit changed from 878ed3a0794d123c46d7cb9ea48ad93ca2d07348 to 98f56421ef86a05d7663bcad818c9709f78a4d24
comment:24 Changed 6 years ago by
 Status changed from needs_work to needs_review
ok, back to needs review. I have added some doc about back and forth conversion to permutations.
comment:25 Changed 6 years ago by
Why did you put the INPUT
block one kilometer away in Permutation.runs
?!
comment:26 Changed 6 years ago by
 Commit changed from 98f56421ef86a05d7663bcad818c9709f78a4d24 to 854de651af7850b6e6c7387c7b54a7544eec7b4f
Branch pushed to git repo; I updated commit sha1. New commits:
854de65  trac #18247 bad formatting

comment:28 Changed 6 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
pong!
comment:29 Changed 6 years ago by
 Branch changed from u/chapoton/18347 to 854de651af7850b6e6c7387c7b54a7544eec7b4f
 Resolution set to fixed
 Status changed from positive_review to closed
comment:30 Changed 5 years ago by
 Commit 854de651af7850b6e6c7387c7b54a7544eec7b4f deleted
Why was a new class derived from tuple
rather then something inheriting from SageObject
??? It now triggers a warning included in doctest by #20667
comment:31 Changed 5 years ago by
Inheriting from tuple is forbidden?
More interesting: what is the warning that was not here before?
comment:32 Changed 5 years ago by
comment:33 Changed 5 years ago by
The problem is that this error will not be solved by inheriting from SageObject
since we need to initialize the content of the tuple... The inheritance from tuple
is here for speed (the methods use __hash__
and __eq__
).
Does the same warning show up with the following?
sage: class A(tuple): ....: def __init__(self, a): ....: tuple.__init__(a) sage: a = A([1,2,3])
It works without any warning in IPython console...
New commits:
trac #18345 implement the shard intersection order of type A