Opened 5 years ago

Closed 4 years ago

Last modified 3 years ago

#18347 closed enhancement (fixed)

implement the shard intersection order on permutations

Reported by: chapoton Owned by:
Priority: minor Milestone: sage-6.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 5 years ago by chapoton

  • 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

New commits:

5d0cf22trac #18345 implement the shard intersection order of type A

comment:2 Changed 5 years ago by darij

You might have forgotten to git-add the main file?

comment:3 Changed 5 years ago by git

  • Commit changed from 5d0cf22c73b983f3b59d2dd154205d78f0a2e7c8 to c8d90002fe00c2ace0fa56abd7b035974645ed38

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

c8d9000trac #18347 main file was forgotten

comment:4 Changed 5 years ago by chapoton

oops, indeed, I was a bit too quick

Do you think that descending_runs should be integrated into runs ?

comment:5 Changed 5 years ago by darij

I don't know -- this seems to be a matter of taste.

comment:6 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_work

Hello,

  1. In decreasing_runs why are you creating a list to return a tuple? You would better use
    return tuple(tuple([n + 1 - i for i in r]) for r in s_bar.runs())
    
  1. What is the point of the cached_function on shard_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
    
  1. This
    dico1 = {}
    # conversion: integer -> index of run in r1
    for i, bloc in enumerate(r1):
        for j in bloc:
            dico1[j] = i
    
    can be
    dico1 = {j:i for i,bloc in enumerate(r1) for j in bloc}
    

Vincent

Last edited 5 years ago by vdelecroix (previous) (diff)

comment:7 Changed 5 years ago by git

  • Commit changed from c8d90002fe00c2ace0fa56abd7b035974645ed38 to e32ecc3a9702cc7ab69ba180eb75f02623418186

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

e32ecc3trac #18347 some of the reviewer's minor comments

comment:8 follow-up: Changed 5 years ago by 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 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 ; follow-up: Changed 5 years ago by vdelecroix

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.

  1. runs and decreasing_runs should return the same data. It is currently list for one of them and tuple for the other.
  1. Why did you wrote the following comment in shard_compares?
    # We assume that r1 has less runs than r0
    
  1. 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 pairs
    sage: 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 5 years ago by vdelecroix

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 5 years ago by git

  • Commit changed from e32ecc3a9702cc7ab69ba180eb75f02623418186 to 88b08d58b257dbaa72ab98f027cc5023d7224a2a

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

88b08d5trac #18347 more reviewer comments, still not the main one

comment:12 follow-up: Changed 5 years ago by 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 ?

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 5 years ago by vdelecroix

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 5 years ago by git

  • Commit changed from 88b08d58b257dbaa72ab98f027cc5023d7224a2a to 70cf5e89ef4898cc519204e55fbcdfe797215894

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

c57e836Create a ShardPosetElement
79d2e2bMerge branch 'public/18347' into 6.7.b4
d3375c0trac #18347 as_tuple option for runs
f250108trac #18347 ok for the ShardPosetElement class
70cf5e8trac #18347 more serious doctesting

comment:15 Changed 5 years ago by git

  • Commit changed from 70cf5e89ef4898cc519204e55fbcdfe797215894 to db7c51a51a7e37d39a5ee015772d5cdc3e254e2d

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

db7c51atrac #18347 more explanations in the doc

comment:16 Changed 5 years ago by chapoton

  • Status changed from needs_work to needs_review

I have added some explanations. Enough ?

comment:17 follow-up: Changed 5 years ago by vdelecroix

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

  1. it would be better if it inherits from tuple (i.e. remove the p attribute and add tuple.__init__(self, p) in the constructor). Then remove the __hash__ and the __repr__ (they are already fine in tuple)
  1. Implement the various operators __le__, __lt__, __gt__, __ge__ and check that it is coherent (this should be ok for __eq__ and __ne__ inherited from tuple)
  1. Moreover, in __le__ you can not assume that self and other 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")
    
  1. Do you want to keep all attributes of ShardPosetElement public as they are?

Vincent

comment:18 Changed 5 years ago by git

  • Commit changed from db7c51a51a7e37d39a5ee015772d5cdc3e254e2d to 878ed3a0794d123c46d7cb9ea48ad93ca2d07348

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

d82ebd8trac #18347 inherit from tuple
878ed3atrac #18347 remove connected_parts

comment:19 in reply to: ↑ 17 ; follow-up: Changed 5 years ago by chapoton

Hello

What does connected_parts is doing in the git branch?

Well, I removed it. Could go in another ticket maybe.

  1. it would be better if it inherits from tuple (i.e. remove the p attribute and add tuple.__init__(self, p) in the constructor). Then remove the __hash__ and the __repr__ (they are already fine in tuple)

Done

  1. Implement the various operators __le__, __lt__, __gt__, __ge__ and check that it is coherent (this should be ok for __eq__ and __ne__ inherited from tuple)

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.

  1. Moreover, in __le__ you can not assume that self and other 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

  1. 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 5 years ago by vdelecroix

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 follow-up: Changed 5 years ago by 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..

comment:22 in reply to: ↑ 21 Changed 5 years ago by vdelecroix

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 5 years ago by git

  • Commit changed from 878ed3a0794d123c46d7cb9ea48ad93ca2d07348 to 98f56421ef86a05d7663bcad818c9709f78a4d24

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

707450fMerge branch 'u/chapoton/18347' into 6.7.rc0
98f5642trac #18347 a little more doc about conversion to permutations

comment:24 Changed 5 years ago by chapoton

  • 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 5 years ago by vdelecroix

Why did you put the INPUT block one kilometer away in Permutation.runs?!

comment:26 Changed 5 years ago by git

  • Commit changed from 98f56421ef86a05d7663bcad818c9709f78a4d24 to 854de651af7850b6e6c7387c7b54a7544eec7b4f

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

854de65trac #18247 bad formatting

comment:27 Changed 4 years ago by chapoton

  • Milestone changed from sage-6.7 to sage-6.8

ping ?

comment:28 Changed 4 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

pong!

comment:29 Changed 4 years ago by vbraun

  • Branch changed from u/chapoton/18347 to 854de651af7850b6e6c7387c7b54a7544eec7b4f
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:30 Changed 3 years ago by novoselt

  • 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 3 years ago by vdelecroix

Inheriting from tuple is forbidden?

More interesting: what is the warning that was not here before?

comment:33 Changed 3 years ago by vdelecroix

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

Note: See TracTickets for help on using tickets.