Opened 10 years ago

Closed 9 years ago

# Implementation of permutohedron intervals

Reported by: Owned by: giraudo sage-combinat major sage-5.10 combinatorics Permutations; Permutohedron sage-5.10.beta1 Samuele Giraudo, Frédéric Chapoton Frédéric Chapoton, Nathann Cohen N/A

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

Apply:

### 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: ↓ 4 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)

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

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