AbstractPermutation interface?

[kalmarek]

There are some users who would like to see some compatibility between different implementations of permutations. I'm the author of one of those (https://github.com/kalmarek/PermutationGroups.jl) which is more about permutation groups than just about permutations.

In particular I created a simple ("raw") Perm type https://github.com/kalmarek/PermutationGroups.jl/blob/master/src/Perms/perm_images.jl#L2-L22 which essentially stores the vector images (+pointer to its inverse, +lazily computed cycle decomposition, all thread safe :). On top of this I implemented the parent group-aware Permutation https://github.com/kalmarek/PermutationGroups.jl/blob/master/src/perm_group.jl#L48-L51

They both follow so called "AbstractPermutation" interface as seen here: https://github.com/kalmarek/PermutationGroups.jl/blob/master/src/Perms/abstract_perm.jl#L3-L32

so they can be both mixed at will, with consistent results (that is hopefully:)

I'd be willing to separate this interface to AbstractPermutations.jl package so that both Permutations.jl and PermutationGroups.jl work together. Would you be willing to accept such dependency and implement the required functions? As the interface is pretty minimal it will not be much of a burden I suppose.

@jmichel7 has also Perms.jl and PermGroups.jl which could benefit from agreeing and implementing a common permutation interface.

[scheinerman]

Dear @kalmarek : I'd be fine with making Permutation a subtype of a new AbstractPermutation type. Tell me a bit more about what changes I might need to make to implement the interface. I don't have a ton of bandwidth, but am agreeable to working on it.

[kalmarek]

Dear @scheinerman, If you're fine with accepting such change, I can volunteer to implement it. Let's wait a bit for Jean to know if he wants to participate in this standardization efforts ;)

[jmichel7]

Hello, I just had time to look at your AbstractPermutation interface. I have three remarks

abstract type AbstractPermutation <: GroupElement end

Is no-go for me, this is the Magma/Oscar philosophy, I have nothing like GroupElement type. To be clear for me a plain integer or a plain matrix can be element of a group, they have no need to be encapsulated in an abstract GroupElement type. So please put it elsewhere than the AbstractPermutation interface.

The second remark is that degree has a different meaning for different people. The meaning you give is what is called LargestMovedPoint in GAP (largest_moved_point in my implementation). In GAP the degree is rather the length of the data vector. I think in Magma all permutations must belong to a group and the degree is a property of the parent group, not of the permutation. I decided because of these ambiguities not to define degree in my implementation. The only place it occurs in my implementation is that it is a keyword of the constructor, used to build a permutation where the internal length m is bigger than the length n of the given vector (by appending n+1:m), which even if the name is disputable is a useful facility I think.

Lastly what you called inttype I called eltype. Disputable again but we should look at precedents, if any.

[jmichel7]

Some more comments

If I understand you call perm a method to retrieve the underlying data vector from a permutation. I call this vec. Again debatable.

My type is a parametric type Perm{T} where T is what you call the inttype. It is always possible to derive a parametric type from a non-parametric abstract type, but I wonder why you did not chose a parametric abstract type?

[kalmarek]

Dear @jmichel7, rather than debating the names I'd be happier to get a rather straight answer to the question if you are willing to participate in the effort for an interchangeable permutations. This part

Is no-go for me, this is the Magma/Oscar philosophy, I have nothing like GroupElement type.

suggests that you are not. I'd appreciate a clear answer without side-tracking into the naming/ideological issues.

Please note that implementing some interface forces you neither to change any of your methods, nor to modify how you write your code. Whether you want to use the interface methods in your code that's an issue of your personal taste and I will neither persuade nor dissuade you from doing this.

---

It seems to me, that all what you said above implies that there are (literally!) no technological issues for you to implement the interface:

• since Your Perm does not have prescribed supertype (except All) it does not disrupt you at all to make it a subtype of AbstractPermutation <: GroupElement; (well, maybe except the loss of some purity ;)
• since you did not define degree you can do it without changing a single line of your code;
• you can simply define inttype by re-directing to eltype;
• you can simply not define perm since the default will work just fine.

To summarize: You can pragmatically implement the interface by changing literally less than 10 lines of your code.

As I understand that you may have some ideological issues with accepting such interface, I'm fine with this and therefore happy to take a straight No as an answer. But my aim here is to provide software usable to other people (which includes making an effort for some interoperability) and not to debate the ideological issues.

---

For the other issues you mentioned:

GroupElement is not part of the Oscar, it is defined here: https://github.com/kalmarek/GroupsCore.jl/blob/f90a9fee9c9b6182efe40d453982732f66ab4a27/src/GroupsCore.jl#L7 in my own package;

My type is a parametric type Perm{T} where T is what you call the inttype. It is always possible to derive a parametric type from a non-parametric abstract type, but I wonder why you did not chose a parametric abstract type?

Because not all permutations are vectors of images of 1:n; Even in this very package you can find a beautiful example of CompiledPermutation.

Lastly what you called inttype I called eltype. Disputable again but we should look at precedents, if any.

If I understand you call perm a method to retrieve the underlying data vector from a permutation. I call this vec. Again debatable.

Of course You may continue to using vec and eltype without any issue in your code. And note that not every permutation is a vector of its images, so that is not what perm is doing.

[jmichel7]

I am probably not communicating well. First, let me say that I would find extremely useful to agree on common generic interfaces for Groups, Permutations, and other concepts. But the devil is in the details.

On your point: GroupElement is not part of the Oscar, it is defined here:

I spent several days in Kaiserslautern in September 2022 to talk to Max Horn. We discussed among other things the possibility of my adopting the Group interface. There is a technological issue: I define Group, actually Group{T}, where T is the type of the elements of the group. Thus I cannot derive from your Group. If you define instead AbstractGroup I could derive Group{T}<:AbstractGroup.

Now, he agreed indeed GroupElement is a serious problem: this definition is unnecessary to have a common AbstractGroup or AbstractPermutation interface; if I adopt this definition people will not understand that I follow the GAP and not the Magma/Oscar philosophy and this will be probably the source of many misunderstandings in any communication with me in the future. It is even a technological problem: my Groups can have elements which are plain matrices, or be of any other Julia type which represent objects which can be multiplied and have no relationship with Oscar, so to say that elements of groups must be GroupElements would seriously restrict the range of my groups. So the existence of GroupElement is a technological problem for me to adopt an AbstractGroup interface. It may not be a technological problem for permutations, but the above remarks explain why I feel like it is one.

Now for your other comments: yes, if there are no technical problems I can adopt your interface in 10 seconds. But are you not willing to discuss with me the design? I do not appreciate to have something put down my throat without any discussion possible. I don't see anywhere a justification of the details of your design.

[kalmarek]

I agree there might be some technological issues with you adapting the group interface; If you have a proposal of changes to the interface please open an issue with the description of requested changes at GroupsCore.jl. Arguably an issue here is not the correct place to discuss those.

However the discussion here is about abstract permutation interface and I would rather stick to the topic.

More to the point, in a few days I will create a preliminary "AbstractPermutations.jl" package to share and start a discussion. And if you don't think we can reach a consensus there you may simply decide not to implement the interface, don't worry I will not touch any of your repositories, you'll have to do it yourself! ;)

[kalmarek]

I started work on the interface in this repository: https://github.com/kalmarek/AbstractPermutations.jl

[scheinerman]

I took a look at the code and am surprised to see so much. When this is working, can you tell me what I need to do in Permutations? It looks overwhelming!

[kalmarek]

@scheinerman no worry, It's not that much!

Example implementation

There are just three methods to be implemented:

• constructor from images (with a boolean check=true to perform validation)
• degree(p) - return the minimal n such that p ∈ Sym(n) (for the identity it is 1)
• Base.^(i::Integer, p) the action on the set of natural numbers. Here the assumption is that p is a finitely supported bijection ℕ → ℕ, so e.g. (if p is stored as the image of 1:n, for i outside 1:n we have i^p == i.

Here is an example implementation in 37 lines: https://github.com/kalmarek/AbstractPermutations.jl/blob/main/test/perms_by_images.jl#L3-L40

What you get for free

What you receive for implementing those methods is:

• interoperability with other implementations
• group arithmetic (* (multiple args), inv, conj) as defined here
• a cycle decomposition and related show methods
• a few basic functions defined for permutations (sign, parity, permtype, firstmoved(p, range), fixedpoints(p, range), nfixedpoints(p, range), order
• parsing of permutations in cycle notation: Base.parse(MyPermutationType, "(1,2,3)(3,4)") is returns (1,2,4,3).
• Everything else that is described here: https://kalmarek.github.io/AbstractPermutations.jl/dev/

---

If macros are your thing then there is macro @perm that just redirects to parse. If you wish you could then write (with Perm type from the example implementation above)

   julia> macro permu8_str(cycles)
           return :(parse(Perm{UInt8}, $cycles))
       end
   @perm8_str (macro with 1 method)

   julia> permu8"(1,2,3)(3,4)"
   (1,2,4,3)

   julia> typeof(ans)
   Perm{UInt8}

[kalmarek]

I took a look at the code and am surprised to see so much. When this is working, can you tell me what I need to do in Permutations? It looks overwhelming!

also, as i have written at the beginning, I can implement this for Permutations.jl package.

[jmichel7]

It seems to me that your AbstractPermutations is not a minimal compatibility package, but a much more extended one representing your idea of how to write permutations.

By the way, I reiterate my opposition to using the term degree for the largest moved point. Exporting this name means in particular that you cannot load simultaneously this package and any package implementing polynomials.

My permutations would not pass your tests, and here are some details.

If I were to use degree for largest_moved_point, I would fail the test where you define the degree of the identity permutation to be 1. Why not 0? As a mathematician, I would have expected you to make a more consistent choice. The fact that for you cycles(identity)=[[1]] is perhaps a consequence but is inconsistent with the printing of identity as ().

I suppose your firstmoved is my smallest_moved_point. Again it should be 0 and not 1 for the identity. The fixedpoints and nfixedpoints seem to operate on 1:degree. This not very useful if you consider permutations in a permutation group of degree n. This is a case where the "implementation detail" of what is the actual length of the internal image vector would be a more pertinent parameter.

My Perms do not pass the test where the constructor taking a Vector{Int} checks its argument for validity. For me this constructor is almost exclusively used when programming some code internal to the permutations package, and does not check in order to be fast. The most common constructor for the user is using the cycle decomposition like Perm(1,2,3)*Perm(4,5) or perm"(1,2,3)(4,5)". It is these last constructors which are checked.

Another divergence is that for you action like 1^p preserves the type of the constant 1. Rather, in my implementation the result is always of what you call the inttype of the permutation. This is both for having this operation as fast as possible and for consistency. For example, the cycles of a Perm{UInt8} are Vector{UInt8}.

The sign function is usual, but not your parity function which could be omitted. Similarly, for conjugating permutations, the notation a^bfor inv(b)*a*b is standard, but not overloading for the same purpose the function conj, which could be omitted.

You check that permutations can be hashed, which is indeed useful in order to be able to use them as keys in Dicts. I claim that they should also have an isless method, in order to be sortable (many algorithms are faster using sorting rather than hashing). Lexicographical order of image vectors does fine for isless.

I have much more to say but that's enough for now.

[kalmarek]

@jmichel7 As far as I can see none of your comment applies to Permutations.jl and all of it applies to AbstractPermutations.jl. If I am right in this regard I'd appreciate very much if you could open an issue in AbstractPermutations.jl to keep the discussion on the design local to that package.

[jmichel7]

I did that. Note that your comment applies basically to every message of the current discussion

[kalmarek]

@scheinerman To continue this discussion: The package is here https://github.com/kalmarek/AbstractPermutations.jl the documentation is here: https://kalmarek.github.io/AbstractPermutations.jl/dev/

I think the biggest issue with implementing the interface is the difference in some assumptions:

• AbstractPermutations model the permutations as elements of {\lim}_{to_n} Sym(n), i.e. all permutations can be multiplied regardless of their "degree" because they live in some Sym(k) together
• Permutations.Permutation can be only multiplied when they reside in the the same Sym(n) as defined by the length of their underlying arrays. This results in somehow interesting failures of tests, e.g.

  import Permutations.Permutation
  id = Permutation([1,2,3])
  @test isone(id)
  @test isone(one(id))
  @test one(id) == id
  @test isone(id*one(id))

  With the last two failing with

  
  julia> @test one(id) == id
  Test Failed at REPL[30]:1
  Expression: one(id) == id
  Evaluated: () == (1)(2)(3)

julia> @test isone(idone(id)) Error During Test at REPL[33]:1 Test threw exception Expression: isone(id one(id)) Cannot compose Permutations of different lengths

Please let me know if you are willing to change the convention of `Permutations.jl` to the one of `AbstractPermutations.jl`. If so I we continue, if not let me abandon this project ;)

[scheinerman]

Gosh, I'm sorry but the answer is "no". I understand your rationale, but it's doesn't mesh with my view of how Permutations should work. A permutation is a bijection from a set to itself. So one should be able to compose permutations that act on different sets. I think I'd like to withdraw my module from consideration. I thought your AbstractPermutation type would be generic enough that I could just tag my Permutation as a subclass without any other changes. That is, I would move my implementation of AbstractPermutation out of my package and just rely on your proposed one.

[kalmarek]

@scheinerman sure, no problem!

There is also other possibility, namely that we modify the tests to accommodate for fixed-length permutations (i.e. always construct permutations of fixed length there).

With this modification I found another problem/incompatibility: namely the only three tests that are failing now are like this:

a = P([2, 1, 3]) # (1,2)
b = P([2, 3, 1]) # (1,2,3)

@test a * b == P([3, 2, 1]) # (1,2)*(1,2,3) == (1,3)
@test b * a == P([1, 3, 2]) # (1,2,3)*(1,2) == (2,3)

According to what I know GAP, PermGroups.jl, PermutationGroups.jl, AbstractAlgebra.jl, Oscar.jl and now also AbstractPermutations.jl implement the convention tested above that (1,2)*(1,2,3) = (1,3), i.e., action on the right 1^((1,2)*(1,2,3)) = 2^(1,2,3) = 3 whereas Permutations.jl implement (1,2)*(1,2,3) = (2,3), i.e., action on the left ((1,2)*(1,2,3))(1) = ((1,2))(2) = 1

Would you be willing to change this?

[scheinerman]

I'm not sure what changes you'd like to see. Sorry! I've only been following this tangentially. I'm willing to consider a modest "to do list" if you'd send me what you'd like to see.

[kalmarek]

@scheinerman It's a very modest todo list:

1. Changing this line

   @inbounds dat = [p.data[q.data[k]] for k = 1:n]

   to

   @inbounds dat = [q.data[p.data[k]] for k = 1:n]

   is what is needed.

[scheinerman]

@kalmarek Well, that would be super easy to change! But first, won't that change the result of a calculation p*q to q*p? For me, permutations are functions and so (p*q)(k) (evaluation of the permutation p*q on an element k should be the same as p(q(k)). Will this change disrupt that?

[kalmarek]

That is precisely what needs to be changed;

Functions act on the set of positive integers on the left whereas in AbstractPermutations.jl permutations act on the right, hence k^(p*q) = (k^p)^q. It's the action on the right that is implemented in GAP, PermutationGroups, PermGroups, Oscar, AbstractAlgebra.jl, … (See also my comment just above).

If this is an interoperability package we need to fix some consistent conventions ;)

[scheinerman]

Eek. I'm sorry, but this is not what I expected. I wasn't following the discussion. I am aware that x^f notation exists and means f(x), but it's not standard for most mathematicians. I think this will be a significantly breaking change that I'm not willing to make.

There's some bloat in my Permutations package that I'd be comfortable removing. For example, Coxeter form. So I can likely restructure so that Permutation is not a subtype of AbstractPermutation thereby freeing up that name for you to use as you wish.

Reaction?

[jmichel7]

The notation x^f is not the usual notation in mathematics book, but it appears in all programming languages which have a permutation type.

[kalmarek]

@scheinerman It's fine; No need to worry about Permutations.[Abstract]Permutation name; Your package can stay safely outside AbstractPermutations.jl.

In mathematics books they almost always pick left actions (hence function evaluation), but for computational purposes the right actions are almost always better.