Permutation as product of (Coxeter) generators?

[dlfivefifty]

Is it possible to convert a Permutation to a product of (Coxeter) generators s_i?

[dlfivefifty]

Here's a quick implementation using a sort:

coxetergenerator(n, i) = Permutation([1:i-1; i+1; i; i+2:n])

decompose(P::Permutation) = decompose!(Permutation(copy(P.data)))
function decompose!(P::Permutation)
    n = length(P)
    s = [coxetergenerator(n,k) for k=1:n]
    data = P.data
    ret = Permutation[]
    issorted([1,2,3,4])
    while !issorted(data)
        for k=1:n-1
            if data[k] > data[k+1]
                data[k], data[k+1] =  data[k+1], data[k]
                push!(ret, s[k])
            end
        end
    end
    reverse!(ret)
end

P = RandomPermutation(6)
    @time ret = decompose(P)

*(ret...)  == P # true

I'll try to make a PR soon.

[scheinerman]

This is cool. But can we call the function something a tad more descriptive such as CoxeterDecomposition ?

[scheinerman]

One more thought. Might it be better if the return is a Vector of Tuple{Int,Int}'s? Something like this: [ (1,2), (4,5), (2,3) ]

[dlfivefifty]

No need for a Tuple, an Int will do.

There really should be an AbstractPermutation type with CoxeterGenerator <: AbstractPermutation

[scheinerman]

I like your idea of creating a CoxterGenerator type. Then if p is a Permutation, we create its Coxter form with cg = CoxterGenerator(p). Conversely, Permutation(cg) would recover the original Permutation.

[dlfivefifty]

I would only use CoxterGenerator for the generators s_i = (i,i+1). I'd imagine the following types:

abstract type AbstractPermutation end
struct CoxeterGenerator <: AbstractPermutation
    n::Int
    i::Int
end
Permutation(P::CoxeterGenerator) = Permutation([1:P.i-1; P.i+1; P.i; P.i+2:P.n])

struct CoxeterDecomposition <: AbstractPermutation
    terms::Vector{CoxeterGenerator} # TODO: How do you make sure this decomposition is unique?
end

*(A::CoxeterGenerator, B::CoxeterGenerator) = CoxeterDecomposition([A,B])
*(A::CoxeterGenerator, B::CoxeterDecomposition) = CoxeterDecomposition([A; B.terms])
*(A::CoxeterDecomposition, B::CoxeterGenerator) = CoxeterDecomposition([A.terms; B])
*(A::CoxeterDecomposition, B::CoxeterDecomposition) = CoxeterDecomposition([A.terms; B.terms])

Permutation(P::CoxeterDecomposition) = *(Permutation.(P.terms)...)
CoxeterDecomposition(P::Permutation) = # the code above

[dlfivefifty]

We could also have

struct CyclePermutation <: AbstractPermutation
   cycles::Vector{Vector{Int}}
end