Closed jmichel7 closed 11 months ago
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.
The intention is to create an interoperability package. For this I guess arithmetic, constructors and degree are necessary.
Parsing and IO are just things we all have written (for better or worse) so i thought it might be good to just put it in one common package. For the other functions
order
is there so that we all inherit from the same function (in GroupsCore
)permtype
and sign
are there as they depend only on cycle decomposition (which is already defined for io)I consider the interface consisting of 3 methods pretty minimal. Do you have a proposal with even narrower set of methods to implement?
By the way, I reiterate my opposition to using the term degree for the largest moved point.
If you read the docstring of degree
you'll notice it is not defined as the "largest moved point". It is the minimal n
such that p
can be regarded as an element of Sym(n)
but not of Sym(n-1)
.
Exporting this name means in particular that you cannot load simultaneously this package and any package implementing polynomials.
Is it exported? As far as I understand, it is not and I don't intend to export it either.
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?
Again, degree
is not the largest moved point and since groups have to be non-empty as sets Sym(0)
does not seem to be a well defined concept ;). So degree(id)==1
is perfectly consistent with both the docstring and the mathematics.
As written in the docstring, AbstractPermutations
operate on a range 1:n
(This is also true for your PermGroups.Perms
-- https://github.com/jmichel7/Perms.jl/blob/178dc75304d238901d0717c85d6caf8d7ab72c39/src/Perms.jl#L6). As far as I know 0
does not belong to 1:n
so it makes little sense to me to return 0
as a largest moved point. A more appropriate would be to return the empty set, which is usually denoted by nothing
in julia. Coincidentally firstmoved(id)
does indeed return nothing
, for mathematical consistency.
As a side note, according to your definition of action
https://github.com/jmichel7/Perms.jl/blob/main/src/Perms.jl#L412
0^p
results in silent out-of-bounds garbage read which you may read as "moving" ;)
(that's of course a joke, but you should rather fix this).
The fact that for you cycles(identity)=[[1]] is perhaps a consequence but is inconsistent with the printing of identity as ().
cycles(id) == [[1]]
is perfectly consistent with the definition of degree
.
Strictly speaking indeed we should print (1)
. However you may recall from early pre-algebra classes that it is also customary to write the identity permutation as ()
;)
Jokes aside, if this is a serious objection of yours, I'm willing to print (1)
if all other objections have been resolved.
I suppose your firstmoved is my smallest_moved_point. Again it should be 0 and not 1 for the identity.
See my comment about above; 0
does not belong to 1:degree(p)
and therefore nothing
is returned as no points in the range are moved by id
(and not 1
as you suggest :). smallest_moved_point
makes sense only if the second argument to firstmoved
is ordered. If you prefer to use smallest_moved_point
in your code you can implement it using firstmoved
trivially.
I believe that it makes sense to have a more general building blocks in the interface and let the other packages implement more specialized ones.
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.
I come to conclusion that neither fixedpoints
nor nfixedpoints
should not have the default second argument as it relies on implicit datum (such as your n
stored as a length of images vector). I will correct this soon. It is better to provide explicit ranges (or iterables) to those functions explicitly.
This is supposed to be an abstract interface without implementation details leaking in. No implicitly stored notion of parent group please ;)
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.
You can write the constructor of your Perm
to accept, yet ignore the second argument.
My usage is the opposite: users often define permutations of large objects and want to compute with the resulting (relatively small) permutation groups. Therefore they have neither cycle string available nor is tuple input a viable solution (degrees are often in thousands and more).
We seem to both agree that the validation of user imput is important.
Whenever a permutation is constructed from external data the input should be validated. If the input has already been validated (e.g. these are already constructed permutations), then the validation can be skipped. This is done here e.g. in arithmetic. We seem to agree here.
I believe the best place for doing validation is the default constructor (with a switch). This is where we seem to disagree, correct?
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.
Can you share any benchmarks confirming that this has any performance implications? For type stability one branch will contain casting to some type anyway.
The rationale for this decision is mathematical.
A group action is a map F : G×Ω → Ω
such that for every p ∈ G
the restriction of F
to {p}×Ω
is a bijection (+some conditions).
Therefore if we start with x ∈ Ω
, the result x^p
must belong to Ω
, rather than to some set defined by p
.
Preserving the type of x
seemed closer to the mathematical definition, especially that 256^one(Perm{UInt8})
should not throw but just return 256
.
For example, the cycles of a Perm{UInt8} are Vector{UInt8}.
As far as I know cycles of the example implementation of Perm
also should return vectors of UInt8
:
julia> p = perm8"(1,2,3)(4,5)"
(1,2,3)(4,5)
julia> typeof(p)
Perm{UInt8}
julia> collect(AbstractPermutations.cycles(p))
2-element Vector{SubArray{UInt8, 1, Vector{UInt8}, Tuple{UnitRange{Int64}}, true}}:
[0x01, 0x02, 0x03]
[0x04, 0x05]
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.
I have no hard feelings about neither parity
or conj
.
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.
Please implement a prototype and open a pull request!
I have much more to say but that's enough for now.
Hopefully I addressed all your comments. If you have more please share.
And now the final joke:
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.
I suppose your firstmoved is my smallest_moved_point. Again it should be 0 and not 1 for the identity.
Do you even remember what you return "for consistency"? https://github.com/jmichel7/Perms.jl/blob/178dc75304d238901d0717c85d6caf8d7ab72c39/src/Perms.jl#L351 https://github.com/jmichel7/Perms.jl/blob/178dc75304d238901d0717c85d6caf8d7ab72c39/src/Perms.jl#L354
As a mathematician writing code I would have expected you not rising objections to functions that are perfectly consistent with your own, on the base of incompatibility ;D
Jokes aside: please don't be offended, but also please don't waste my and your time on discussions "for discussions sake". Said that, Let's move on to more productive dialogue.
As far as I know 0 does not belong to 1:n so it makes little sense to me to return 0 as a largest moved point. A more appropriate would be to return the empty set, which is usually denoted by nothing in julia. Coincidentally firstmoved(id) does indeed return nothing, for mathematical consistency.
I would say that both 0
and nothing
are consistent choices, while 1
is not. Historically my functions smallest_moved_point and largest_moved_point returned nothing
for the identity; I found one day that it was convenient that largest_moved_point
returned 0
since it allowed to find the largest_moved_point
of a list l
of permutations by maximum(largest_moved_point.(l))
. I changed that day largest_moved_point
and forgot to change the same day smallest_moved_point
. Of course, the fact that these two functions do not do the same thing is a bug that I will fix.
Let's move on to more productive dialogue.
A productive dialogue is when both agree to move their position where they become closer. A point on which I would accept to move is renaming smallest_moved_point
and largest_moved_point
to firstmoved
and lastmoved
. They are more Julian names (well first_moved
and last_moved
would also be Julian). Note that if you change degree
to lastmoved
, you would recover a lost symmetry between your names.
Let me try to be concise. You commented on several points:
degree
vs. largest_moved_point
/lastmoved
: Since your post above is the third in a row that mixes those two concepts, let me clarify for the third time:
degree(p)
is the minimaln
such thatp
can be regarded as an element ofSym(n)
but not ofSym(n-1)
.
I would be grateful if you finally acknowledge that these are different concepts, or explain why do you still think they are the same.
I would say that both 0 and nothing are consistent choices, while 1 is not.
It is terrific, since neither your Perm
nor AbstractPermutations
return 1
for this case. AbstractPermutations
return nothing
and Perms
used to do so. We can argue if returning 0
(outside of the domain) is really consistent, or is it just convenient (the argument with maximum(...)
). The maximum(...)
case is however a weak one, as there are much faster (and consistent) ways to write it...
Moreover
degree
be exported Solved (as it will not be exported)nfixedpoints
, fixedpoints
(without the default second argument) are more general and no longer clash with your versions which use implicit parent permutation group Ongoing (Do we agree that these definitions don't clash with yours?).typeof(i) == typeof(i^p)
. Since one conversion has to take place, I consider the example of 256^one(Perm{UInt8})
a strong argument for this solution. Ongoing (If you don't have benchmarks on this I'd prefer to have it Solved).parity
and conj
can be removed Solvedisless
! Ongoingfirst_moved/firstmoved
and last_moved/lastmoved
are fine with me. If we decide for using underscores then [n]fixedpoints
should also be renamed (and probably some others?). Which one do you choose?And of course we will be printing the identity as (1)
when everything is resolved :)
It occurs to me that there is some general misunderstanding what an "interface" really is.
If you implement AbstractPermutation
API it means that you neither need to
smallest_moved_point
), norWhat it means is that if a user passes your Perms to any external function that uses only the functions derived from the API is going to produce the expected result. That's it. Therefore I don't understand your opposition to using some names/conventions that DON'T EVEN CLASH with your package.
It occurs to me that there is some general misunderstanding what an "interface" really is.
Well, your repository confuses me on this. There is nothing marked explicitly "AbstractPermutation API", so I looked at the files
src/abstract_perm.jl
and abstract_perm_API.jl
thinking they are the API. Am I mistaken? It is not clear if anything is exported in your API. I repeat that there should be somewhere an explanation of the rationale for the various points of the design to make the whole thing more convincing. The output of our discussions should help in principle toward that.
If you implement AbstractPermutation API it means that you neither need to rename any of your functions (e.g. smallest_moved_point), nor change their semantics, nor stop using them, nor finally that you start using the API within your code!!! Do you understand this?
Yes, I understand this. But I am only willing to work with you if you are willing to consider me as an equal partner and not someone who has no right to give his opinions. It should be possible to reach consensus on many points, including the conclusion that no consensus is possible on some points. For my part, I invented not much, I mainly am following the design of GAP3/GAP4 for permutations which has been carefully evolved over several years in the beginning of the 90's (not by me).
I discuss now only 2 points since I do not have time to write more tonight.
degree(p) is the minimal n such that p can be regarded as an element of Sym(n) but not of Sym(n-1).
I would be grateful if you finally acknowledge that these are different concepts, or explain why do you still think they are the same.
Can you give me a permutation such that degree(p)!=lastmoved(p)
?
My main objection for degree
is that it does not correspond to anything in the literature or on internet. I did not find a notion of degree for individual permutations. There is a notion of degree for permutation groups, but it does not have the same meaning: it is the cardinality of the set Ω on which it operates, but nothing says that it has to operate without fixed points or that the largest integer moved would equal the cardinality of Ω.
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.
The rationale for this decision is mathematical. A group action is a map F : G×Ω → Ω such that for every p ∈ G the restriction of F to {p}×Ω is a bijection (+some conditions). Therefore if we start with x ∈ Ω, the result x^p must belong to Ω, rather than to some set defined by p. Preserving the type of x seemed closer to the mathematical definition, especially that 256^one(Perm{UInt8}) should not throw but just return 256.
Well, the rationale for my/GAP design is also mathematical: I a view a Perm{T}
where T<:Integer
operating legitimately only on sets whose elements are of type T
. It can operate on a value i
of type T_1
iff convert(T,i)
does not error. The result of applying a Perm{T}
is of course of type T
.
Can you share any benchmarks confirming that this has any performance implications? For type stability one branch will contain casting to some type anyway.
Well, most often I apply a Perm{T}
to an integer of type T
and there is no conversion. Not very informative, but here is a benchmark:
my Perms:
julia> p=Perm(Int16.(sortperm(rand(1:100,100))));@btime (1:100).^$p;
92.214 ns (1 allocation: 256 bytes)
your Perms:
julia> p=Perm(Int16.(sortperm(rand(1:100,100))));@btime (1:100).^$p;
107.326 ns (1 allocation: 896 bytes)
Not much difference but the 15% difference seems to persist over other integer types and other sizes of permutations.
Here is a small GAP session
gap> G:=SymmetricGroup(0);
Group( () )
gap> Elements(G);
[ () ]
gap> p:=G.identity;
()
gap> LargestMovedPoint(p);
0
gap> NrMovedPoints(p);
0
gap> Cycles(p); # no cycles
[ ]
SymmetricGroup(0)
appears in many places in the mathematics literature. It is a limit case of an automorphism group
of structures where it makes sense that n
can become 0.
Can you give me a permutation such that degree(p)!=lastmoved(p) ?
one(Perm)
. The first one is 1
in accordance to its definition; the second is undefined/null/fail/not_found as signified by customary nothing
in julia.
I believe that GAP convention originates from the the times where functions had to return element of consistent type (so no nothing
).
My main objection for degree is that it does not correspond to anything in the literature or on internet.
I hope you realize that is an argument for using it here, since
So far I see only opposition of yours, without a single constructive proposal; So let me propose something: how about mindegree
(with the same semantics, I want AbstractPermutation
s be supported on 1:n
).
At this point though I'm happy to agree that we disagree on what permutations should be and part our ways.
As for the benchmark: The size difference in allocations suggest that what you are looking at is difference in alloc
:
julia> @btime UInt16.(1:100);
67.981 ns (1 allocation: 256 bytes)
julia> @btime UInt.(1:100);
89.092 ns (1 allocation: 896 bytes)
~30ns difference; Repeating what you did:
julia> @btime (1:100).^$(Ref(p1));
75.319 ns (1 allocation: 256 bytes)
julia> @btime (1:100).^$(Ref(p2));
101.171 ns (1 allocation: 896 bytes)
that is about the same.
And indeed the effect is gone if you write a non-allocating benchmark:
julia> f!(v, p) = (for i in eachindex(v); v[i] = i^p end; v);
julia> v = collect(1:100);
julia> @benchmark f!($v, $p1) # PermGroups.Perm
BenchmarkTools.Trial: 10000 samples with 983 evaluations.
Range (min … max): 57.266 ns … 390.131 ns ┊ GC (min … max): 0.00% … 0.00%
Time (median): 62.168 ns ┊ GC (median): 0.00%
Time (mean ± σ): 63.761 ns ± 4.604 ns ┊ GC (mean ± σ): 0.00% ± 0.00%
▄▁▃ ▁▆▅▆▄▇▆▇▄ ▁ ▅▆█▅▅ ▁ ▂
▂▆████▆▇▆▆██████████▇█▆█▆█▆██▇████████▅▇▇█▅█▆████▆▆▂▆▄▆▆▆▅▅▅ █
57.3 ns Histogram: log(frequency) by time 73.3 ns <
Memory estimate: 0 bytes, allocs estimate: 0.
julia> @benchmark f!($v, $p2) # perms_by_images.jl Perm
BenchmarkTools.Trial: 10000 samples with 984 evaluations.
Range (min … max): 55.362 ns … 86.663 ns ┊ GC (min … max): 0.00% … 0.00%
Time (median): 57.278 ns ┊ GC (median): 0.00%
Time (mean ± σ): 57.627 ns ± 1.649 ns ┊ GC (mean ± σ): 0.00% ± 0.00%
▂ ▃▅▄█▇▆▇▂▁ ▁ ▁ ▁ ▂
▃▅▆▇████████████▅█▇████▆▆▅▅█▅▇█▇▆▅▆▇▃▆▇▆█▄▁▅▁▄▅▁▄▄▄▅▅▇▆▆▇▆▆ █
55.4 ns Histogram: log(frequency) by time 66.4 ns <
Memory estimate: 0 bytes, allocs estimate: 0.
Inspecting the assembly of both functions it turns out that #perms_by_images.jl
is actually shorter (and saves at least one jump since it doesn't throw!).
At this point though I'm happy to agree that we disagree on what permutations should be and part our ways.
Well, if you are still up to a small effort, what would be most useful is that you try to answer my question
It occurs to me that there is some general misunderstanding what an "interface" really is.
Well, your repository confuses me on this. There is nothing marked explicitly "AbstractPermutation API", so I looked at the files
src/abstract_perm.jl and abstract_perm_API.jl
thinking they are the API. Am I mistaken? It is not clear if anything is exported in your API. I repeat that there should be somewhere an explanation of the rationale for the various points of the design to make the whole thing more convincing. The output of our discussions should help in principle toward that.
I really don't understand what is what in your repository. I was expecting a minimal specification of a few lines, and I find a lot of text and files whose role I don't exactly understand.
An interface is a minimal set of functions that once implemented correctly allow a much larger code-base to be build around. The classical interface in julia is AbstractArray which is defined by
AbstractArray
size
andgetindex
.Through these few functions many other functions are defined (only using the basic ones + some assumptions e.g. 1
-based indexing). These come "for free" to the implementer who can just use them, or overload at will (maintaining the semantics).
This allows to run matrix-matrix products without writing one, but also e.g. an Arnoldi eigensolver which accepts not only Arrays
, but also abstract LinearMaps
.
MathOptInterface
is a different (very elaborate) way of defining an interface for a (convex) solver so that it can be used seamlessly from the JuMP
optimization framework.
In the same spirit AbstractPermutations.jl
define a minimal (also 3
functions) interface which allows some very basic functionality (firstmoved
, order
, etc.) but other packages may implement more complex functions such as stabilizer chain computations, backtracking through the sc tree etc. that work for all implementation instances, regardless of implementation details.
The problem is that the way you wrote your package, it is not true that only the 3 functions of the interface must agree for the rest to be compatible (pass your tests).
[
Base.:^(i::Integer, σ::APerm)
](@ref ^(::Integer, ::AbstractPermutation))
does not specify whether ^(i::T,Perm{T'})
where T,T'
are integral types is of type T or T' (or something else). So it looks compatible with my package but is not since it impacts your tests. Similarly, you derive a lot of properties from
- [
degree(σ::APerm)
](@ref degree) the minimald ≥ 1
such thatσ
fixes allk ≥ d
.
This results in my permutations failing your tests; my permutations would succeed your tests if your definition was
degree(σ::APerm)
](@ref degree) the minimal d ≥ 0
such that σ
fixes all k ≥ d
.The problem of course is not the definition itself, but all the consequences you derive, so it is misleading to say the interface is just 3 functions. The existence of symmetric_group(0)
is really important. My problem is that my main package Gapjm
(which will be called Chevie
when it will be registered in one month or two, since it recovers the functionality of this GAP packge), consists of about 40000 lines of code + more than 200000 lines of data in the form of programs transpiled from GAP (that you can find in the directory src/tbl
). The transpiled data would still probably work if I change ^
to follow your (non-written) specification, since integers do not have subtypes in GAP. But the transpiled data would definitely fail if I adopt the consequences of your belief in the non-existence of symmetric_group(0)
.
If ones uses degree(σ)
when needing an integer i
such that i^σ != i
then this is going to be followed by some code that assumes i
is a natural number.
Suppose you use in that code an @inbounds
statement because you know σ
is not the identity unless you made a mistake.
In case you make a mistake, the inbounds will either result in a segmentation fault which is already quite annoying.
But it could also result in modifying an arbitrary memory which might result in heisenbug that takes hours to debug.
The advantage of nothing
is that you will have a nice error with a nice stacktrace which makes is easy to trace down what happens.
Now, I can see that in some other use cases, the same code could just work with 0
so you don't have to make any exception while if it returned nothing, you have to replace this into 0
which can be annoying.
One solution could be to have one function for each use case:
degree
would return 0
for the identity elementlast_moved
is the equivalent of first_moved
but in the other direction. For consistency with first_moved
, findfirst
and findlast
, it would return nothing
for the identity element. From a readability point of view, from last_moved
you would expect to receive a point that is actually moved so 0
feels odd.By default, the interface could implement degree(σ) = something(last_moved(σ), 0)
so that an implementation of permutations don't have to implement both.
What do you think of this, would that suit Chevie
?
The main problem for me is that the identity permutation id
keeps behaving as in GAP. That is
cycles(id)
is the empty listid
prints as ()
(not consistent since the cycles being empty it should print as the empty string, but this way of printing the identity is traditional)In GAP there are no two different functions degree
and last_moved
, there is only the function LargestMovedPoint
used everywhere. I really do not like degree
since it evokes for me a different meaning, so I will keep using lastmoved
(or last_moved
?). Having last_moved(id)
return nothing
instead of 0
may cause errors in my transpiled data, but at least errors easy to find, and which can be fixed as you point out by writing something(last_moved(σ), 0)
. But last_moved(id)
being equal to 1
would be horrendous (just like the consequences drawn from degree(id)==1
in the current package).
While I am writing, a point I have not yet examined.
There is a function called CycleType
or CycleStructure
which is related to permtype
in AbstractPermutations
. But its use determines what it returns, which is slightly different from the result of permtype
: cycletype(σ)
returns a partition describing the conjugacy class of σ
, and this partition includes the 1
s corresponding to trivial cycles. So to make sense this needs a second argument cycletype(σ,1:n)
to specify the domain on which σ
operates. Here it is useful that the second argument be an arbitrary AbstractVector
and not only an integer. For instance, the Weyl group of type B_n
has two orbits acting on the roots, and an invariant of a conjugacy class is the union of the cycletypes on both orbits: you would use cycletype(σ,o_1)
and cycletype(σ,o_2)
where o_1
and o_2
are the two orbits.
This packages doesn't have to mimick GAP for the sake of compatibility. Also, it doesn't prevent you to keep the largest_moved_point
defined in your package.
Yes, this package does not have to mimick GAP. But do you think it is unreasonable that the identity prints as ()
(I think it did at some stage). And that the identity does not have any (non-trivial) cycle?
I'm just talking about the degree here
You said above
- degree would return 0 for the identity element
If that was the case I think I would be fine
Hey guys, I see you have a lot of fun discussing here ;)
@jmichel7 it would be best if you had stated at the beginning that you have 40k lines of GAP3-style code that you carry on your back. That means essentially that you will be unhappy with anything that is not GAP3-compatible because those 40k lines of code fix you in stone.
Since we want to follow julia conventions here (it's a julia package after all) and not just formalize Your GAP3 interface I suggest we settle this discussion and trod along our own paths. I see no need for them to be aligned.
Just to reiterate for future uses: you don't define degree
and this package doesn't define largest_moved_point
, so there is no technological issue with you adapting the interface.
But I accept that you reject it on ideological grounds and see no further gain to either of us to continue this discussion.
In the future if users are confused about the incompatibility we can always direct them to read the discussion here.
See also #5.
I do not agree with your summary. I do not reject anything on ideological grounds. But I don't pass your tests.
Some like typeof(x^p)=typeof(x)
I could modify my package to pass. But to have identity printed differently than () or
cycles(identity) not being the empty list I cannot modify.
I see that today PermutationGroups
prints identity as ()
. So there is only left cycles(identity)
that you decided on
ideological grounds to be (1)
which cause a problem.
@jmichel7 the only thing that is tested that AP.cycles
returns [[1]]
, not any of your functions; It still seems that it is not clear to you what an interface is. You can define and use your own PermGroups.cycles
according to your liking if the AP.cycles
doesn't satisfy your needs.
EDIT: You might be interested in changes incorporated in pull requests from #1 to #5, as you seem to argue on the first version instead of the latest.
Thank you for informing about the pull request #5. I will bring my repository in conformity with typeof(i^p)=typeof(i) and if nothing more changes my problems with the identity permutation are solved.
Then the last obstacle is that my constructor does not check the input by default. I am not sure what to do about that. I certainly want that in all functions where I define arithmetic on permutations I do not have to write something as cumbersome as Perm(v;check=false)
all over the place. For some other types I have an inner constructor like Perm_
which does not check. If I do that in this case I will have to document and export this inner constructor so that users can use it.
I registered a new version 0.2.10 of my package where
largest_moved_point
to last_moved
and smallest_moved_point
to first_moved
vec
to perm
^
so that typeof(i^p)==typeof(i)
I think you're moving too fast ;) the first version is not yet released!
I think vec
(with its meaning) should stay in PermGroup
s and should not be replaced by perm
! The latter is to create the most efficient representation as an AbstractPermutation
for low level computations, not a vector. E.g. if you have permutations stored as products of cycles you may want to turn them into e.g. words over a generating set before the schreier_sims
. That is what perm
is intended to do.
For future: Probably a better definition in the future will be perm(::Function, p::AbstractPermutation) = perm(p)
so that we can have the option of fine-grained control over different functions.
For future: As for ^
we might also consider turning this into typeof(i^p) == promotetype(typeof(i), AP.inttype(p))
if it ever creates an issue for us.
For future: We might discuss the validation for the next version (v0.2.0
). We can also modify tests and just warn the user that this implementation doesn't validate the input, so should be uses with care.
I thought that perm
made sense since the functions in julia dealing with permutations (sortperm
, invperm
, isperm
) use the word perm
and consider permutations as vectors of integers.
By the way, I don't have your fixedpoints
, but I needed the complement, the moved points, which is traditionally called the support
of the permutation.
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)ab 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.