Implementation of permutohedron intervals

[SamueleGiraudo]

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

Apply:

• attachment: trac_12569-permutohedron_intervals-sg-v2.patch

Component: combinatorics

Keywords: Permutations, Permutohedron

Author: Samuele Giraudo, Frédéric Chapoton

Reviewer: Frédéric Chapoton, Nathann Cohen

Merged: sage-5.10.beta1

Issue created by migration from https://trac.sagemath.org/ticket/12569

[SamueleGiraudo]

Attachment: trac_12569-permutohedron_intervals-sg.patch.gz

Tested on Sage 4.8, combinat branch

[sagetrac-elixyre]

comment:2

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

[fchapoton]

comment:3

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

[hivert]

comment:4

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

[fchapoton]

comment:5

I have added the doc.

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

[fchapoton]

comment:6

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.

[fchapoton]

comment:7

I have added the doctest

[nathanncohen]

comment:8

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

[fchapoton]

comment:9

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)

[nathanncohen]

comment:10

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

[fchapoton]

comment:11

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.

[fchapoton]

Attachment: trac_12569-permutohedron_intervals-sg-v2.patch.gz

[fchapoton]

Work Issues: doc tests

[fchapoton]

comment:12

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

for the bot:

apply trac_12569-permutohedron_intervals-sg-v2.patch

[fchapoton]

Reviewer: Frédéric Chapoton

[nathanncohen]

Changed author from Samuele Giraudo to Samuele Giraudo, Frédéric Chapoton

[nathanncohen]

comment:13

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

[nathanncohen]

Changed reviewer from Frédéric Chapoton to Frédéric Chapoton, Nathann Cohen

[jdemeyer]

Changed work issues from doc tests to none

[jdemeyer]

Merged: sage-5.10.beta1