Opened 10 years ago

Closed 9 years ago

#12569 closed enhancement (fixed)

Implementation of permutohedron intervals

Reported by: giraudo Owned by: sage-combinat
Priority: major Milestone: sage-5.10
Component: combinatorics Keywords: Permutations; Permutohedron
Cc: Merged in: sage-5.10.beta1
Authors: Samuele Giraudo, Frédéric Chapoton Reviewers: Frédéric Chapoton, Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by chapoton)

We implement a new method in the class Permutation which enables to compute the permutations of intervals of the permutohedron.

Apply:

Attachments (2)

trac_12569-permutohedron_intervals-sg.patch (2.9 KB) - added by giraudo 10 years ago.
Tested on Sage 4.8, combinat branch
trac_12569-permutohedron_intervals-sg-v2.patch (8.7 KB) - added by chapoton 9 years ago.

Download all attachments as: .zip

Change History (17)

Changed 10 years ago by giraudo

Tested on Sage 4.8, combinat branch

comment:1 Changed 10 years ago by giraudo

  • Status changed from new to needs_review

comment:2 Changed 10 years ago by elixyre

Like in my previous post... this patch isn't in combinat branch...

comment:3 follow-up: Changed 10 years ago by chapoton

Hello,

could you please add documentation to the first function ? one indirect doctest would be fine, for example,

EXAMPLES:: 	 
    sage: Permutation([2, 1, 4, 5, 3]).right_permutohedron_interval(Permutation([2, 5, 4, 1, 3])) # indirect doctest
    [[2, 1, 4, 5, 3], [2, 1, 5, 4, 3], [2, 4, 1, 5, 3], [2, 4, 5, 1, 3], [2, 5, 1, 4, 3], [2, 5, 4, 1, 3]] 

then the bot will be happy. Cheers,

F

comment:4 in reply to: ↑ 3 Changed 10 years ago by hivert

then the bot will be happy.

But Sphinx, the documentation generator, will be disturbed if you don't put a blank line after EXAMPLE::. So the correct markup is:

EXAMPLES::

    sage: Permutation([2, 1, 4, 5, 3]).right_permutohedron_interval(Permutation([2, 5, 4, 1, 3])) # indirect doctest
    [[2, 1, 4, 5, 3], [2, 1, 5, 4, 3], [2, 4, 1, 5, 3], [2, 4, 5, 1, 3], [2, 5, 1, 4, 3], [2, 5, 4, 1, 3]] 

Florent

comment:5 Changed 10 years ago by chapoton

  • Description modified (diff)

I have added the doc.

patchbot, apply trac_12569-permutohedron_intervals-sg-v2.patch

comment:6 Changed 10 years ago by chapoton

New patch with minor changes, including one doctest for one of the raise exceptions.

There remains to add a doctest for the other raise exception.

comment:7 Changed 10 years ago by chapoton

I have added the doctest

comment:8 Changed 9 years ago by ncohen

  • Status changed from needs_review to needs_info

Helloooooooooooooo !!

Same remark as in #12571 : could you add those new methods to the index ? Besides, wouldn't it be possible to also call "inverse" in the second add_edge(...) line ?

Oh, yeah... Ad wouldn't it make sense to update inversions to index its results from 1 to n instead of 0 to n-1, assuming nobody agrees that permutations should themselves go from 0 to n-1 ?

Nathann

comment:9 Changed 9 years ago by chapoton

Here is a new patch.

I have changed the behavior of inversions, also improving very slightly its speed. Let us see if this causes problems elsewhere.

I do not think one can use .inverse in the second add_edge line

I have added both methods to the index

I have taken the opportunity to make a very light clean up (using pyflakes to remove a few unused import and unused variables)

comment:10 Changed 9 years ago by ncohen

Sorry, I meant "inversions" not "inverse".

for i in xrange(len(other) - 1) for j in xrange(i, len(other)) if other[i] < other[j]]

really looks like a computation of inversions, doesn't it ? O_o

Nathann

comment:11 Changed 9 years ago by chapoton

No, it is a computation of 'not inversions' in fact.

It seems that the change of the behaviour inversions triggers a few doc tests in the rest of sage.. Some in graphs stuff, see the bot report.

Changed 9 years ago by chapoton

comment:12 Changed 9 years ago by chapoton

  • Description modified (diff)
  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_info to needs_review
  • Work issues set to doc tests

new patch, correcting some doctests. There remains other doctests failing.

for the bot:

apply trac_12569-permutohedron_intervals-sg-v2.patch

comment:13 Changed 9 years ago by ncohen

  • Authors changed from Samuele Giraudo to Samuele Giraudo, Frédéric Chapoton
  • Reviewers changed from Frédéric Chapoton to Frédéric Chapoton, Nathann Cohen
  • Status changed from needs_review to positive_review

Helloooooooooooooooo !!!

I again spent a couple of minutes trying to check if there was anything wrong with the graph whose linear extensions you return, but modulo the fact that I am biologically unable to check if it is not "left" instead of "right" and which is the largest among 12 and 21, everything seems good :-D

Good to go !

Nathann

comment:14 Changed 9 years ago by jdemeyer

  • Work issues doc tests deleted

comment:15 Changed 9 years ago by jdemeyer

  • Merged in set to sage-5.10.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.