New Permutations package

[seangrate]

New package implementing a Permutation type by Sean Grate. Its intent is to have a standard and consistent type for permutations as more combinatorics-focused packages get added to Macaulay2. Much of the inspiration for the implemented methods came from the Sage implementation. This also resolves Issue #2581.

[mahrud]

1. Add your package to the =distributed-packages file, otherwise it's basically ignored.
2. I think having both Permutations.m2 and Permutations/Permutations.m2 could lead to hard to decipher errors (e.g. try needsPackage "Permutations" inside the Permutations directory). My suggestion would be to put most of the content of Permutations/Permutations.m2 in Permutations.m2, and name the other two files tests.m2 and docs.m2.
3. Typos:

M2/Macaulay2/packages/Permutations/PermutationsDOC.m2:241: postive ==> positive
M2/Macaulay2/packages/Permutations/PermutationsDOC.m2:622: simulataneously ==> simultaneously

[seangrate]

I should also mention that this package includes code for pattern avoidance and is taken directly from the MatrixSchubert package. The idea is that since pattern avoidance is inherent to permutations, it'll go into Permutations, and following the adoption of this package, the MatrixSchubert package might be overhauled to use the Permutation type from this package for consistency.

[pzinn]

One incompatibility with the built-in permutations is that they start at 0, not 1.

[mahrud]

One incompatibility with the built-in permutations is that they start at 0, not 1.

Yes, although MatrixSchubert is also 1-indexed. I realize I'm not the main audience of this, so I don't have a strong opinion. Would it be much harder to check whether a permutation is 0 or 1 indexed in every algorithm? Or maybe have easy to use functions for going forth and back?

[seangrate]

One incompatibility with the built-in permutations is that they start at 0, not 1.

Yes, although MatrixSchubert is also 1-indexed. I realize I'm not the main audience of this, so I don't have a strong opinion. Would it be much harder to check whether a permutation is 0 or 1 indexed in every algorithm? Or maybe have easy to use functions for going forth and back?

I think a good solution would be some sort of configuration option when loading the package. So, it defaults to $1$-indexing, but the user can switch to $0$-indexing if they prefer. Something like needsPackage("Permutations", ZeroIndex=>true).

[mahrud]

Recently I was using permutations (though not through this package) and I thought of a few wish list items, if you have time to implement them:

1. VisibleList_Permutation (and MutableList), Matrix_Permutation and Matrix^Permutation (and MutableMatrix) for permuting elements of lists and columns or rows of matrices.
2. A comparison operator Permutation ? Permutation based on the Bruhat order (is this available elsewhere in M2?)
3. A method to get the poset of Bruhat order and the Hasse diagram of S_n (including maybe a way to get the subposet below or above a given permutation)
4. matrix Permutation to get the permutation matrix (I know permToMatrix in MatrixSchubert does this, but given a Permutation type you could just define matrix on it)

I'm happy to merge this with the 1-based notation if at least item 1 above is implemented.

[d-torrance]

@TheGrateSalmon, @mahrud: What's the status of this PR? Should we include this package in the release as it is, or is still waiting for some changes?

[seangrate]

1. VisibleList_Permutation (and MutableList), Matrix_Permutation and Matrix^Permutation (and MutableMatrix) for permuting elements of lists and columns or rows of matrices.

This is somewhat implemented in the package, though with a different syntax. I think your suggestion makes a bit more sense.

2. A comparison operator Permutation ? Permutation based on the Bruhat order (is this available elsewhere in M2?)

3. A method to get the poset of Bruhat order and the Hasse diagram of S_n (including maybe a way to get the subposet below or above a given permutation)

These items would be wonderful to have. I'm not sure what the best way to display the Hasse diagram would be, however. I don't think I will get around to implementing them in the current release though.

4. matrix Permutation to get the permutation matrix (I know permToMatrix in MatrixSchubert does this, but given a Permutation type you could just define matrix on it)

This also exists as toMatrix, but this syntax makes a bit more sense as well, so it should be an easy change.

@TheGrateSalmon, @mahrud: What's the status of this PR? Should we include this package in the release as it is, or is still waiting for some changes?

I should be able to incorporate some of @mahrud's suggestions this weekend. After that, from my understanding, it sounds like this package will be ready for its initial release.

[d-torrance]

These items would be wonderful to have. I'm not sure what the best way to display the Hasse diagram would be, however. I don't think I will get around to implementing them in the current release though.

There's a hasseDiagram method already in the Posets package that you could use.

[mahrud]

There's a hasseDiagram method already in the Posets package that you could use.

How do I get the poset of $$S_n$$ to begin with?

[d-torrance]

How do I get the poset of S n to begin with?

How's the partial order defined? If it's easy to either list all the pairs $(\sigma,\tau)$ with $\sigma\leq\tau$ or write a function that returns true when $\sigma\leq\tau$, then the poset method should work.

[mahrud]

$S_n$ has $n!$ elements so listing all ordered pairs works but definitely not the optimal solution. The Hasse diagram has far fewer edges but I don't know how many exactly.

[seangrate]

I've added @mahrud's request for VisibleList, though I'm not sure how to do the same for MutableList (mainly because I'm not sure what the expected behavior with something like Bag should be). I've also changed toMatrix to matrix.

S n has n ! elements so listing all ordered pairs works but definitely not the optimal solution. The Hasse diagram has far fewer edges but I don't know how many exactly.

If I am remembering correctly, the Bruhat order gives a graded Hasse diagram with a unique maximal element, the longest word permutation $(n,n-1,\dots,1)$. So, I would think a breadth-first search from that element should be good enough, though this is without thinking about the problem too carefully.

[mahrud]

This looks good! Could you resolve the conflict so the tests can run?