Implementation of permutohedron intervals

[giraudo]

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

Apply:

• trac_12569-permutohedron_intervals-sg-v2.patch

[giraudo]

Tested on Sage 4.8, combinat branch

[elixyre]

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

[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

[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

[chapoton]

I have added the doc.

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

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

[chapoton]

I have added the doctest

[ncohen]

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

[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)

[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

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

[chapoton]

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

for the bot:

apply trac_12569-permutohedron_intervals-sg-v2.patch

[ncohen]

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