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: |
Description (last modified by )
We implement a new method in the class Permutation which enables to compute the permutations of intervals of the permutohedron.
Apply:
Attachments (2)
Change History (17)
Changed 10 years ago by
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
Like in my previous post... this patch isn't in combinat branch...
comment:3 follow-up: ↓ 4 Changed 10 years ago by
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
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
- Description modified (diff)
I have added the doc.
patchbot, apply trac_12569-permutohedron_intervals-sg-v2.patch
comment:6 Changed 10 years ago by
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
I have added the doctest
comment:8 Changed 9 years ago by
- 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
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
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
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
comment:12 Changed 9 years ago by
- 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
- 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
- Work issues doc tests deleted
comment:15 Changed 9 years ago by
- Merged in set to sage-5.10.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
Tested on Sage 4.8, combinat branch