view release on metacpan or  search on metacpan

devel/lib/Graph/Maker/Permutations.pm  view on Meta::CPAN

The default C<rel_type =E<gt> 'transpose'> is graph edges where swapping two
elements in the permutation gives a lexicographically bigger permutation.

    from  x ... y      transpose
     to   y ... x       values x<y                     

        --> 2,1,3 --> 2,3,1 --\
       /         \   ^         v          N => 3
    1,2,3  --------X------->  3,2,1       rel_type => "transpose"
       \         /   v         ^
        --> 1,3,2 --> 3,1,2 --/

Each permutation has binomial(N,2) element pairs, and across all
permutations they are, by symmetry, half smaller-bigger and half
bigger-smaller so

    num edges = N!*N*(N-1)/4
              = 0,0,1,9,72,600,5400,...     (A001809)

=cut

# GP-DEFINE  transpose_num_edges(N) = N!*N*(N-1)/4;
# GP-Test  vector(7,N,N--; transpose_num_edges(N)) == [0,0,1,9,72,600,5400]
#
# The "transpose_..." relation types below restrict to just some transposes so
# are edge subsets of full "transpose".

=pod

=head2 Transpose Cover

Option C<rel_type =E<gt> 'transpose_cover'> restricts to those transposes
which are cover relations of the transposes (so the Hasse diagram).  This
means if a path u -E<gt> z -E<gt> ... -E<gt> v exists then omit direct u
-E<gt> v.  In N=3 this means no edge 123 -E<gt> 321.

        --> 2,1,3 --> 2,3,1 --\
       /         \   ^         v       N => 3
    1,2,3          X          3,2,1    rel_type => "transpose_cover"
       \         /   v         ^
        --> 1,3,2 --> 3,1,2 --/

A cover is when the x...y swap has, between those locations, no values
between x and y.  If such an intermediate t then could do the x,y swap by
three transposes x,t, t,y, x,t, which in each case are lex increases.  This
is seen across the top of N=3 above.  Other combinations using t are
possible too.  The number of covers is

    num edges = sum 1<=i<j<N of N!/(j-i+1)
              = 0,0,1,8,58,444,3708,...    (A002538)

This sum is per David Callan in OEIS A002538.  Elements i and j are to be
swapped.  Those and the i+1,i+2,...,j-1 values between them are ordered
(j-i+1)! ways (within the whole permutation).  But cannot have intermediate
values between i,j.  Perms of i..j with i,j adjacent are only (j-i)!, so
fraction (j-i)!/(j-i+1)! = 1/(j-i+1) of all N! perms.

=cut

# GP-DEFINE  \\ formula per A002538 but starting N=2 at value=1
# GP-DEFINE  transpose_cover_num_edges(N) = /* per A002538 */ \
# GP-DEFINE    if(N<=1,0, (N+1)*transpose_cover_num_edges(N-1) + (N-1)*(N-1)!);
# GP-Test  vector(7,N,N--; transpose_cover_num_edges(N)) == [0,0,1,8,58,444,3708]
#
# new element N at any of N positions
# covers in N-1 still good so N*covers(N-1)
# covers i to N has new N bigger
# so x ... N with N at any position
#
# sum N* for i<j<N
# then j=N
# vector(10,N, sum(i=1,N-1, N!/(N-i+1)))
# vector(10,N, sum(i=1,N-1, N!/(N-i+1)) + N*transpose_cover_num_edges(N-1))
# A001705 gen Stirling 
# vector(10,N, sum(i=1,N-1, N!/(N-i+1)) - transpose_cover_num_edges(N-1))

=pod

An "inversion" in a permutation is a pair of out-of-order elements, so x...y
with xE<gt>y.  A cover transpose increases the number of inversions by +1.
A transpose of x,y with xE<lt>y goes to yE<gt>x so +1 inversions.  If an
element tE<gt>y is between them then +1 inversion for new t,x position but
-1 for new y,t.  Similarly the other way for an element smaller E<lt>x.  An
element t between x and y values would be +2 inversions.  So an equivalent
definition is to take cover as step by +1 inversion.

=head2 Transpose Adjacent

Option C<rel_type =E<gt> 'transpose_adjacent'> restricts to swapping an
adjacent pair of elements.  This is the weak Bruhat order.

    from  x y     transpose_adjacent
     to   y x        values x<y

        --> 2,1,3 --> 2,3,1 --\
       /                       v       N => 3
    1,2,3                     3,2,1    rel_type => "transpose_cover"
       \                       ^
        --> 1,3,2 --> 3,1,2 --/

Each of the N-1 non-last elements has a next neighbour and by symmetry they
are half smaller-bigger and half bigger-smaller so

    num edges = N!*(N-1)/2, or 0 if N=0
              = 0,0,1,6,36,240,1800,...     (A001286)

=cut

# GP-DEFINE  transpose_adjacent_num_edges(N) = if(N==0,0, N!*(N-1)/2);
# GP-Test  vector(7,N,N--; transpose_adjacent_num_edges(N)) == \
# GP-Test    [0,0,1,6,36,240,1800]

=pod

=head2 Transpose Cyclic

Option C<rel_type =E<gt> 'transpose_cyclic'> restricts to transposing an
adjacent pair of elements, with adjacent including wraparound so first and
last can swap.