Opened 9 years ago

Closed 7 years ago

#11410 closed enhancement (fixed)

01 sequence or east-north sequence for partitions

Reported by: pdehaye Owned by: sage-combinat
Priority: minor Milestone: sage-5.8
Component: combinatorics Keywords: partition
Cc: sage-combinat Merged in: sage-5.8.beta4
Authors: Paul-Olivier Dehaye Reviewers: Frédéric Chapoton, Nathann Cohen, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #13605 Stopgaps:

Description (last modified by tscrim)

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:

Attachments (3)

Change History (27)

comment:1 Changed 8 years ago by pdehaye

  • Status changed from new to needs_review

suggestions for the name welcome

comment:2 Changed 8 years ago by ncohen

  • Status changed from needs_review to needs_work

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

comment:3 Changed 7 years ago by chapoton

  • Description modified (diff)
  • Status changed from needs_work to needs_review

Apply trac_11410-zero_one_sequence_partitions-pod.v2.patch

Here is patch with some corrections.

comment:4 Changed 7 years ago by chapoton

  • Authors set to Paul-Olivier Dehaye

comment:5 Changed 7 years ago by chapoton

  • Reviewers set to Frédéric Chapoton, Nathann Cohen

comment:6 Changed 7 years ago by chapoton

Apply trac_11410-zero_one_sequence_partitions-pod.v2.patch

comment:7 Changed 7 years ago by tscrim

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

comment:8 Changed 7 years ago by andrew.mathas

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

Andrew

comment:9 Changed 7 years ago by chapoton

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.

comment:10 Changed 7 years ago by chapoton

Apply trac_11410-zero_one_sequence_partitions-pod.v2.patch

comment:11 follow-up: Changed 7 years ago by darij

@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?

Last edited 7 years ago by darij (previous) (diff)

comment:12 in reply to: ↑ 11 Changed 7 years ago by tscrim

Replying to darij:

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

Last edited 7 years ago by tscrim (previous) (diff)

comment:13 Changed 7 years ago by chapoton

  • Dependencies set to #13605

comment:14 Changed 7 years ago by tscrim

  • Status changed from needs_review to needs_work

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

comment:15 Changed 7 years ago by chapoton

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.

comment:16 Changed 7 years ago by chapoton

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

Apply trac_11410-zero_one_sequence_partitions-pod.v2.patch

comment:17 Changed 7 years ago by chapoton

  • Status changed from needs_work to needs_review

comment:18 Changed 7 years ago by tscrim

  • Cc sage-combinat added
  • Description modified (diff)
  • Reviewers changed from Frédéric Chapoton, Nathann Cohen to Frédéric Chapoton, Nathann Cohen, Travis Scrimshaw

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

comment:19 Changed 7 years ago by tscrim

For patchbot:

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

comment:20 follow-up: Changed 7 years ago by chapoton

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.

comment:21 Changed 7 years ago by tscrim

Done.

For patchbot:

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

comment:22 Changed 7 years ago by tscrim

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

comment:23 in reply to: ↑ 20 Changed 7 years ago by tscrim

  • Status changed from needs_review to positive_review

Replying to chapoton:

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.

comment:24 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.8.beta4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.