Opened 3 years ago

Closed 3 years ago

Last modified 3 years ago

#18628 closed enhancement (fixed)

Implementation of Foata bijection on words

Reported by: aschilling Owned by:
Priority: major Milestone: sage-6.8
Component: combinatorics Keywords: words, permutations, days65
Cc: sage-combinat Merged in:
Authors: Anne Schilling Reviewers: Franco Saliola, Mike Zabrocki
Report Upstream: N/A Work issues:
Branch: 85e64f0 (Commits) Commit:
Dependencies: Stopgaps:

Description

The Foata bijection is implemented for permutations, but it also exists on words with repeated entries. This ticket implements this.

Change History (18)

comment:1 Changed 3 years ago by aschilling

  • Branch set to u/aschilling/foata-18628
  • Commit set to 045b42ece609458057019fc95fb87d6c93d92f19

New commits:

045b42eimplementation of Foata bijection on words

comment:2 Changed 3 years ago by git

  • Commit changed from 045b42ece609458057019fc95fb87d6c93d92f19 to f4ae45c789c09b3ba4028406cd5193f7c1cb185a

Branch pushed to git repo; I updated commit sha1. New commits:

f4ae45cadded major index and inversion numbers to FiniteWords

comment:3 Changed 3 years ago by aschilling

  • Keywords days65 added

comment:4 Changed 3 years ago by git

  • Commit changed from f4ae45c789c09b3ba4028406cd5193f7c1cb185a to 83b1442a15d5ad8258494f41578cbeed28710e97

Branch pushed to git repo; I updated commit sha1. New commits:

83b144218628: typo

comment:5 Changed 3 years ago by aschilling

  • Status changed from new to needs_review

New commits:

83b144218628: typo

comment:6 follow-up: Changed 3 years ago by zabrocki

I am not sure if the name de_standardize is clear. I kind of sounds like a German standardization. What do you think about the name standardize_inverse, unstandardize or un_standardize?

comment:7 Changed 3 years ago by MariaMonks

Glad you are implementing this generalization! I will take a look. :)

comment:8 Changed 3 years ago by saliola

The code needs a slight modification to deal with words that are not lists.

sage: w = Word('121314')                                                                                                                                                 
sage: w.foata_bijection()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-19-9c058c286599> in <module>()
----> 1 w.foata_bijection()

/projects/24aaf173-6355-4bc5-9515-ee1048da3ea3/sage-dev-images/sage-6.8.beta3/local/lib/python2.7/site-packages/sage/combinat/words/finite_word.pyc in foata_bijection(self)
    610         """
    611         s = self.standard_permutation()
--> 612         weight = [self.count(i) for i in range(1,max(self)+1)]
    613         return (s.foata_bijection()).de_standardize(weight)
    614 

TypeError: cannot concatenate 'str' and 'int' objects

comment:9 in reply to: ↑ 6 Changed 3 years ago by aschilling

Replying to zabrocki:

I am not sure if the name de_standardize is clear. I kind of sounds like a German standardization. What do you think about the name standardize_inverse, unstandardize or un_standardize?

We took a poll at Sage Days 65 and the majority of people is in favor of destandardize.

comment:10 Changed 3 years ago by saliola

Also, a documentation request: could you add a reference to a paper where the bijection is defined and proved?

comment:11 Changed 3 years ago by saliola

  • Status changed from needs_review to needs_work

comment:12 Changed 3 years ago by zabrocki

  • Branch changed from u/aschilling/foata-18628 to public/aschilling/foata/18628
  • Commit changed from 83b1442a15d5ad8258494f41578cbeed28710e97 to 74d20fce0d240bbacd888e66f0651b651fffc484

I made some minor changes to the documentation.


New commits:

74d20fcchanges to see also links

comment:13 Changed 3 years ago by git

  • Commit changed from 74d20fce0d240bbacd888e66f0651b651fffc484 to b9ae7b3c83cd820055b48eff985e72d2a09d6b7d

Branch pushed to git repo; I updated commit sha1. New commits:

b9ae7b3implemented change from de_standardize to destandardize

comment:14 follow-up: Changed 3 years ago by aschilling

  • Branch changed from public/aschilling/foata/18628 to u/aschilling/foata-18628
  • Commit changed from b9ae7b3c83cd820055b48eff985e72d2a09d6b7d to 85e64f0a83ae7af07a5294d70665702acea2c24d
  • Reviewers set to Franco Saliola, Mike Zabrocki, SageDays65 Crowd
  • Status changed from needs_work to needs_review

New commits:

5fc3cf818628: fixed Franco's comments on different alphabets
85e64f018628: imported Mike's review changes

comment:15 in reply to: ↑ 14 Changed 3 years ago by aschilling

I hope all issues are now fixed!

comment:16 Changed 3 years ago by zabrocki

  • Status changed from needs_review to positive_review

I think that this looks fine and all tests pass.

comment:17 Changed 3 years ago by vbraun

  • Branch changed from u/aschilling/foata-18628 to 85e64f0a83ae7af07a5294d70665702acea2c24d
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:18 Changed 3 years ago by jdemeyer

  • Commit 85e64f0a83ae7af07a5294d70665702acea2c24d deleted
  • Reviewers changed from Franco Saliola, Mike Zabrocki, SageDays65 Crowd to Franco Saliola, Mike Zabrocki

Real author names only please.

Note: See TracTickets for help on using tickets.