NAME
Graph::Maker::Permutations - create transposition graph and more
SYNOPSIS
use Graph::Maker::Permutations;
$graph = Graph::Maker->new ('permutations', N => 4);DESCRIPTION
Graph::Maker::Permutations creates Graph.pm graphs where each vertex is a permutation of the integers 1..N. N=0 is understood as an empty permutation.
num vertices = N! = 1,1,2,6,24,120, ... (A000142)The default is the transpositions graph (see "Transpose" below).
Vertex Names
Option vertex_name_type chooses the vertex name style. The default vertex_name_type => 'perm' is a list of integers 1 to N.
4,1,3,2 perm
1 2 3 4 position, so 1->4, 2->1, etcOption vertex_name_type => 'cycles' is list of cycles
(1,4,2)(3) cycles In the usual way a cycle like (1,4,2) means permute 1->4, 4->2, 2->1. For vertex names the cycles have their smallest element first and in order of the smallest element.
Comma
Option comma => "string" is the separator to use between quantities in the vertex names. The default is comma ",".
When N < 10, permutation terms are single digits and omitting the comma might be preferred for compact viewing. N=10 ambiguity would be at 10! = 3628800 many vertices which is probably too big to be practical, but may be just in reach of a fast machine with plenty of memory.
Transpose
The default rel_type => '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)Transpose Cover
Option rel_type => 'transpose_cover' restricts to those transposes which are cover relations of the transposes (so the Hasse diagram). This means if a path u -> z -> ... -> v exists then omit direct u -> v. In N=3 this means no edge 123 -> 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.
An "inversion" in a permutation is a pair of out-of-order elements, so x...y with x>y. A cover transpose increases the number of inversions by +1. A transpose of x,y with x<y goes to y>x so +1 inversions. If an element t>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 <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.
Transpose Adjacent
Option rel_type => '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)Transpose Cyclic
Option rel_type => 'transpose_cyclic' restricts to transposing an adjacent pair of elements, with adjacent including wraparound so first and last can swap.
from x y or [start] x ... y [end] transpose_cyclic
to y x [start] y ... x [end] values x<yFor N=3 this is the same as all transpose, but in bigger N there are fewer edges. Each of the N elements has a next neighbour wrapping around and by symmetry they are half smaller-bigger and half bigger-smaller so
num edges = N!*N/2, or 0 if N=1
= 0,0,2,9,48,300,2160,... (A074143)Relation Direction
For a directed graph, edges are in the direction of the rules above. This is the default rel_direction => 'up', being a lexicographic increase in the perm. Direction "down" is the opposite, the same as $graph->transpose. Direction "both" is edges both ways. An undirected graph is just one edge between vertices in all cases.
FUNCTIONS
$graph = Graph::Maker->new('permutations', key => value, ...)-
The key/value parameters are
N => integer, represented trees size graph_maker => subr(key=>value) constructor, default Graph->new rel_type => string "transpose" (default), "transpose_cover" "transpose_adjacent", "transpose_cyclic" rel_direction => string "up" (default), "down", "both" vertex_name_type => string "perm" (default), "cycles" comma => string, default "," or empty ""Other parameters are passed to the constructor, either the
graph_makercoderef orGraph->new().If the graph is directed (the default) then edges are only in the "successor" direction for the given
rel_type.
HOUSE OF GRAPHS
House of Graphs entries for graphs here include
https://hog.grinvin.org/ViewGraphInfo.action?id=1310 etc
all rel_type
1310 N=0 and N=1, singleton
19655 N=2, path-2
transpose
84 N=3
1277 N=4, Reye graph
33628 N=5
transpose_cover
938 N=3
33636 N=4
33638 N=5
transpose_adjacent
670 N=3, 6-cycle
1391 N=4, truncated octahedral
transpose_cyclic
84 N=3, same as all transposes
1292 N=4OEIS
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this tree include
http://oeis.org/A000142 (etc)
A000142 num vertices, N!
transpose
A001809 num edges
A165208 num paths start to end
transpose_cover
A002538 num edges
A061710 num paths start to end
(= num max-length paths in transpose)
transpose_adjacent
A001286 num edges
A007767 num intervals
A005118 num paths start to end
transpose_cyclic
A074143 num edges
onepos
A067318 num edges, total transpositionsIn the above, "num intervals" is the number of pairs of vertices $u to $v where $v is reachable from $u. In a lattice this means $u and $v are comparable. $u reachable from $u itself is included (an empty path), so sum 1 + $graph->all_successors($u) over all $u.
SEE ALSO
Graph::Maker, Graph::Maker::Catalans
HOME PAGE
http://user42.tuxfamily.org/graph-maker-other/index.html
LICENSE
Copyright 2019, 2020, 2021 Kevin Ryde
This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.