01 sequence or east-north sequence for partitions

ffc49b07-0ea9-4bb7-be61-8d0cf4baa5a0 commented 13 years ago

Adds a method to the partition class that returns the 01 sequence of the partition (the sequence of north or east steps taken along the boundary of the partition). Since this is really an biinfinite sequence starting with 0000000 and ending with 11111111, this should return a a finite list of 0s and 1s, starting for any (non-empty) partition with a 1 and ending with a 0.

Apply:

Depends on #13605

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: partition

Author: Paul-Olivier Dehaye

Reviewer: Frédéric Chapoton, Nathann Cohen, Travis Scrimshaw

Merged: sage-5.8.beta4

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

ffc49b07-0ea9-4bb7-be61-8d0cf4baa5a0 commented 13 years ago

Attachment: trac_11410-zero_one_sequence_partitions-pod.patch.gz

ffc49b07-0ea9-4bb7-be61-8d0cf4baa5a0 commented 13 years ago

comment:1

suggestions for the name welcome

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago

comment:2

Helloooooo !!!

Some remarks/questions :

Is there really no name for this "0-1 sequence" in the litterature ? `:-/"
We try to keep our lines to 80 characters at most
The documentation of "from_zero_one" can not be found easily by the user : these informations should also be given in the documentation of the Partition class. If the user wants to build a partition this way, he/she first has to consult the help of Partition, then read the code, then load the from_zero_one" method manually, then consult its help :-P
The "INPUT:" field is not a Sphinx field, so only one semicolumn is sufficient. Same thing for OUTPUT.
I did not really understand of defining the 01 sequence as biinfinite to say just afterwards that it is equivalently defined by a finite sequence.
I do not find the current definition "that clear". As it is easy to compute, would it be worth giving a formal definition of the transformation from partition to 0-1 sequence in the documentation ?

Nathann

fchapoton commented 12 years ago

comment:3

Apply trac_11410-zero_one_sequence_partitions-pod.v2.patch

Here is patch with some corrections.

fchapoton commented 12 years ago

Description changed:

--- 
+++ 
@@ -1,2 +1,3 @@
-add a method to the partition class that would return the 01 sequence of the partition (the sequence of north or east steps taken along the boundary of the partition). since this is really an biinfinite sequence starting with 0000000 and ending with 11111111, this should return a a finite list of 0s and 1s, starting for any (non-empty) partition with a 1 and ending with a 0. 
+Adds a method to the partition class that returns the 01 sequence of the partition (the sequence of north or east steps taken along the boundary of the partition). Since this is really an biinfinite sequence starting with 0000000 and ending with 11111111, this should return a a finite list of 0s and 1s, starting for any (non-empty) partition with a 1 and ending with a 0.

+Apply [attachment: trac_11410-zero_one_sequence_partitions-pod.v2.patch](https://github.com/sagemath/sage-prod/files/10653017/trac_11410-zero_one_sequence_partitions-pod.v2.patch.gz)

fchapoton commented 12 years ago

Author: Paul-Olivier Dehaye

fchapoton commented 12 years ago

Reviewer: Frédéric Chapoton, Nathann Cohen

fchapoton commented 12 years ago

comment:6

Apply trac_11410-zero_one_sequence_partitions-pod.v2.patch

tscrim commented 12 years ago

comment:7

Could you add

sage: Partition(zero_one=[0,0,0,0,1,1,1,1,0,1,0,1,1,1,1,1])
[5, 4]

to from_zero_one() showing that it ignores leading 0's and trailing 1's? Also, I think this should be based on #13072 (it doesn't apply for me after #13072) and possibly #11476 too. I will see if I can find a reference too.

Thanks,

Travis

AndrewMathas commented 12 years ago

comment:8

When I have used these I have called them path sequences or Maya diagrams.

Andrew

fchapoton commented 11 years ago

comment:9

Here is a new patch, rebased on 5.7.beta3.

In my opinion, there remains one problem : the choice of the name.

If nobody comes with a better one, with references, then I think the ticket is good to go, if the light turns green.

fchapoton commented 11 years ago

comment:10

Apply trac_11410-zero_one_sequence_partitions-pod.v2.patch

darijgr commented 11 years ago

comment:11

@name: Richard Stanley (in "The Rank and Minimal Border Strip Decomposition of a Skew Partition", http://arxiv.org/pdf/math/0109092.pdf) calls this the "Comét code" of the partition, probably referring to one of the encodings in Stig Comét's http://www.ams.org/journals/mcom/1955-09-052/S0025-5718-1955-0074954-0/ .

May I suggest implementing a similar back-and-forth conversion for skew partitions and biwords of 0's and 1's? Of course, one could take the Comét code of the inner rim and the outer rim, but then one would have to fumble around with their offsets to make them match, so an implementation in the library would be preferred.

Curiosity question: What is a difference between a normal and an "indirect" doctest?

tscrim commented 11 years ago

comment:12

Replying to @darijgr:

Curiosity question: What is a difference between a normal and an "indirect" doctest?

It's for functions/methods that aren't explicitly called in the doctest. For example Foo._repr_() being called when you execute sage: Foo.

As for the patch, the INPUT: block in indented one too many times. Could you put some of the alternative names in the function's documentation? Also I feel like the formatting would be better in latex formatting `1-0`.

A math/documentation note, these also arise from affine permutations and have connections to k-Schur functions (see k-Schur Functions and Affine Schubert Calculus, pages 24-25, http://arxiv.org/abs/1301.3569 and from this you could also justify calling these plus-minus sequences).

Finally could you rebase this on the (soon to be completed) #13605? I'll do the final review if you rebase it as soon as #13605 is done. Promise.

Thank you,

Travis

fchapoton commented 11 years ago

Dependencies: #13605

tscrim commented 11 years ago

comment:14

This fails to apply for me over #13605:

travis@travis-virtualbox:~/sage-5.7.beta3/devel/sage-combinat/sage/combinat$ sage -hg qpush
applying trac_11410-zero_one_sequence_partitions-pod.v2.patch
patching file sage/combinat/partition.py
Hunk #1 FAILED at 205
Hunk #4 FAILED at 292
Hunk #5 FAILED at 301
Hunk #6 succeeded at 442 with fuzz 2 (offset 41 lines).
Hunk #7 succeeded at 2744 with fuzz 1 (offset 531 lines).
3 out of 7 hunks FAILED -- saving rejects to file sage/combinat/partition.py.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_11410-zero_one_sequence_partitions-pod.v2.patch

fchapoton commented 11 years ago

comment:15

Well, I have not yet rebased the patch, so the hunks are expected. I do not know when I will find time do do that.

fchapoton commented 11 years ago

Attachment: trac_11410-zero_one_sequence_partitions-pod.v2.patch.gz

fchapoton commented 11 years ago

comment:16

Here is a rebased. Still missing things about names..

Apply trac_11410-zero_one_sequence_partitions-pod.v2.patch

tscrim commented 11 years ago

comment:18

Hey Frederic,

I've uploaded a review patch which adds some more info to the documentation. Everything else looks good to me. If you agree with my changes, you can set this to positive review.

Thanks,

Travis

tscrim commented 11 years ago

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

tscrim commented 11 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,7 @@
 Adds a method to the partition class that returns the 01 sequence of the partition (the sequence of north or east steps taken along the boundary of the partition). Since this is really an biinfinite sequence starting with 0000000 and ending with 11111111, this should return a a finite list of 0s and 1s, starting for any (non-empty) partition with a 1 and ending with a 0.

-Apply [attachment: trac_11410-zero_one_sequence_partitions-pod.v2.patch](https://github.com/sagemath/sage-prod/files/10653017/trac_11410-zero_one_sequence_partitions-pod.v2.patch.gz)
+Apply:
+
+- [attachment: trac_11410-zero_one_sequence_partitions-pod.v2.patch](https://github.com/sagemath/sage-prod/files/10653017/trac_11410-zero_one_sequence_partitions-pod.v2.patch.gz)
+- [attachment: trac_11410-zero_one_sequence_partitions-review-ts.patch](https://github.com/sagemath/sage-prod/files/10653018/trac_11410-zero_one_sequence_partitions-review-ts.patch.gz)
+

tscrim commented 11 years ago

comment:19

For patchbot:

Apply: trac_11410-zero_one_sequence_partitions-pod.v2.patch, trac_11410-zero_one_sequence_partitions-review-ts.patch

fchapoton commented 11 years ago

comment:20

maybe you could use the very new arxiv role

:arxiv:`1301.3569`

as introduced in #14011

Otherwise, things look good. I am just waiting for the green light from the bot.

tscrim commented 11 years ago

comment:21

Attachment: trac_11410-zero_one_sequence_partitions-review-ts.patch.gz

Done.

For patchbot:

Apply: trac_11410-zero_one_sequence_partitions-pod.v2.patch, trac_11410-zero_one_sequence_partitions-review-ts.patch

tscrim commented 11 years ago

comment:22

The patchbot was blue (due to #13605). I gave it a kick.

For patchbot:

Apply: trac_11410-zero_one_sequence_partitions-pod.v2.patch, trac_11410-zero_one_sequence_partitions-review-ts.patch

tscrim commented 11 years ago

comment:23

Replying to @fchapoton:

Otherwise, things look good. I am just waiting for the green light from the bot.

Since the patchbot gives the go-ahead (when it doesn't timeout), I'm setting this to positive review.

jdemeyer commented 11 years ago

Merged: sage-5.8.beta4

sagemath / sage

01 sequence or east-north sequence for partitions #11410