Jay Pantone

PermPy

PermPy is a python library for the manipulation of permutations and permutation classes. It is useful for experimentation and forming conjectures, and has played a role in about a dozen publications in the field of permutation patterns.

Download

github repository

Examples

Generating the class of \(1324\)-avoiding permutations up to length 8:

In [1]: from permpy import *

In [2]: C = Av([4231], 8)

In [3]: C
Out[3]:
[Set of 0 permutations,
 Set of 1 permutations,
 Set of 2 permutations,
 Set of 6 permutations,
 Set of 23 permutations,
 Set of 103 permutations,
 Set of 513 permutations,
 Set of 2762 permutations,
 Set of 15793 permutations]

Generating the geometric grid class \(\text{Geom}\left(\begin{array}{rrr}0&1&-1\\1&-1&0\end{array}\right)\) up to length 10, and the guessing the basis of the class:

In [1]: from permpy import *

In [2]: G = GeometricGridClass([[0, 1, -1], [1, -1, 0]], [1,-1,1], [1,-1], max_length=10)

In [3]: G
Out[3]:
[Set of 0 permutations,
 Set of 1 permutations,
 Set of 2 permutations,
 Set of 6 permutations,
 Set of 20 permutations,
 Set of 66 permutations,
 Set of 212 permutations,
 Set of 666 permutations,
 Set of 2060 permutations,
 Set of 6306 permutations,
 Set of 19172 permutations]

In [4]: G.guess_basis(search_mode=True)
       	4 basis elements of length 4   		0.00 seconds
       	3 basis elements of length 5   		0.01 seconds
       	0 basis elements of length 6   		0.04 seconds
       	0 basis elements of length 7   		0.13 seconds
       	0 basis elements of length 8   		0.35 seconds
       	0 basis elements of length 9   		1.21 seconds
       	0 basis elements of length 10  		4.05 seconds
Out[4]: Set of 7 permutations

In [5]: _.show_all()
Out[5]: 'PermSet([ 4 2 3 1 ,  2 1 5 3 4 ,  4 3 1 2 ,  2 1 4 3 5 ,  4 1 2 3 ,  3 1 2 4 ,  3 2 5 4 1 ])'

Find the generating function for the set of permutations that can be generated from the identity using at most two cut-and-paste operations (see Homberger and Vatter):

In [1]: from permpy import *

In [2]: PegPermSet.sortable_by_cut_and_paste(2).enumerate()
Starting to compute downset.
       	Downset done. Contains 32597 peg permutations.
Starting to compactify.
       	Done compactifying. Now contains 23812 peg permutations.
Starting to compute cross sections.
       	Cleaning, finding bases, and loading pairs.
       		 0 of 23812 ...
       		 20000 of 23812 ...
       	Unioning bases.
       		 0 of 23812 ... dict_size = 19235
       	Done computing cross_sections. There are 19235 cross sections.
Starting to compute generating function.
       		 1000 of 19235 	took 0.452915906906 seconds.
       		 2000 of 19235 	took 0.584920167923 seconds.
       		 3000 of 19235 	took 0.544396877289 seconds.
       		 4000 of 19235 	took 0.636564970016 seconds.
       		 5000 of 19235 	took 0.650744915009 seconds.
       		 6000 of 19235 	took 0.585341930389 seconds.
       		 7000 of 19235 	took 0.700680017471 seconds.
       		 8000 of 19235 	took 0.596862077713 seconds.
       		 9000 of 19235 	took 0.732371807098 seconds.
       		 10000 of 19235        	took 1.15763092041 seconds.
       		 11000 of 19235        	took 0.588515996933 seconds.
       		 12000 of 19235        	took 0.458482027054 seconds.
       		 13000 of 19235        	took 0.49985408783 seconds.
       		 14000 of 19235        	took 0.709647893906 seconds.
       		 15000 of 19235        	took 0.540335893631 seconds.
       		 16000 of 19235        	took 0.56786608696 seconds.
       		 17000 of 19235        	took 0.576908826828 seconds.
       		 18000 of 19235        	took 0.832302093506 seconds.
       		 19000 of 19235        	took 0.607397079468 seconds.
       	Done!
Out[2]: x*(x**10 - 5*x**9 - 2*x**8 + 44*x**7 - 24*x**6 - 80*x**5 - 43*x**4 + 11*x**3 - 13*x**2 + 5*x - 1)/(x**7 - 7*x**6 + 21*x**5 - 35*x**4 + 35*x**3 - 21*x**2 + 7*x - 1)

Find the generating function of \(\text{Av}(4123,3214)\) using the Insertion Encoding (see Vatter):

In [1]: from permpy import *

In [2]: I = InsertionScheme([Perm(4123), Perm(3214)])

In [3]: I.build_rules()
       	states to check: 1 ,   nodes in tree: 1 ,   states: 1

Checking: (0,)
(0,) is not reducible
       	states to check: 4 ,   nodes in tree: 1 ,   states: 1

Checking: (1,)
(1,) is not reducible
       	states to check: 3 ,   nodes in tree: 1 ,   states: 1

Checking: (0, 1)
Checking isomorphism (depth=3): (0, 1) <-> (0,)
(0, 1) is reducible to (0,)
       	states to check: 2 ,   nodes in tree: 32 ,   states: 1

Checking: (1, 0)
Checking isomorphism (depth=3): (1, 0) <-> (0,)
(1, 0) is reducible to (0,)
       	states to check: 1 ,   nodes in tree: 46 ,   states: 1

Checking: (0, 1, 0)
(0, 1, 0) is not reducible
       	states to check: 8 ,   nodes in tree: 46 ,   states: 2

Checking: (0, 1, 2)
Checking isomorphism (depth=3): (0, 1, 2) <-> (0, 1)
(0, 1, 2) is reducible to (0, 1)
       	states to check: 7 ,   nodes in tree: 63 ,   states: 2

Checking: (2, 1, 0)
Checking isomorphism (depth=3): (2, 1, 0) <-> (1, 0)
(2, 1, 0) is reducible to (1, 0)
       	states to check: 6 ,   nodes in tree: 80 ,   states: 2

Checking: (0, 2, 1, 0)
Checking isomorphism (depth=4): (0, 2, 1, 0) <-> (0, 1, 0)
(0, 2, 1, 0) is not reducible
       	states to check: 7 ,   nodes in tree: 80 ,   states: 3

Checking: (0, 1, 2, 0)
Checking isomorphism (depth=4): (0, 1, 2, 0) <-> (0, 1, 0)
(0, 1, 2, 0) is not reducible
       	states to check: 8 ,   nodes in tree: 80 ,   states: 4

Checking: (3, 1, 2, 0)
Checking isomorphism (depth=3): (3, 1, 2, 0) <-> (1, 2, 0)
(3, 1, 2, 0) is reducible to (1, 2, 0)
       	states to check: 8 ,   nodes in tree: 112 ,   states: 4

Checking: (1, 2, 0)
Checking isomorphism (depth=3): (1, 2, 0) <-> (1, 0)
(1, 2, 0) is reducible to (1, 0)
       	states to check: 7 ,   nodes in tree: 112 ,   states: 4

Checking: (2, 0, 1, 0)
Checking isomorphism (depth=4): (2, 0, 1, 0) <-> (0, 1, 0)
(2, 0, 1, 0) is reducible to (0, 1, 0)
       	states to check: 6 ,   nodes in tree: 340 ,   states: 4

Checking: (0, 1, 0, 2)
Checking isomorphism (depth=4): (0, 1, 0, 2) <-> (0, 1, 0)
(0, 1, 0, 2) is reducible to (0, 1, 0)
       	states to check: 5 ,   nodes in tree: 458 ,   states: 4

Checking: (0, 2, 1, 3)
Checking isomorphism (depth=3): (0, 2, 1, 3) <-> (0, 2, 1)
(0, 2, 1, 3) is reducible to (0, 2, 1)
       	states to check: 5 ,   nodes in tree: 486 ,   states: 4

Checking: (0, 2, 1)
Checking isomorphism (depth=3): (0, 2, 1) <-> (0, 1)
(0, 2, 1) is reducible to (0, 1)
       	states to check: 4 ,   nodes in tree: 486 ,   states: 4

Checking: (0, 2, 0, 1, 0)
(0, 2, 0, 1, 0) is not reducible
       	states to check: 5 ,   nodes in tree: 486 ,   states: 5

Checking: (3, 0, 1, 2, 0)
Checking isomorphism (depth=4): (3, 0, 1, 2, 0) <-> (0, 1, 2, 0)
(3, 0, 1, 2, 0) is reducible to (0, 1, 2, 0)
       	states to check: 4 ,   nodes in tree: 510 ,   states: 5

Checking: (0, 2, 1, 0, 3)
Checking isomorphism (depth=4): (0, 2, 1, 0, 3) <-> (0, 2, 1, 0)
(0, 2, 1, 0, 3) is reducible to (0, 2, 1, 0)
       	states to check: 3 ,   nodes in tree: 534 ,   states: 5

Checking: (0, 2, 0, 1, 3)
Checking isomorphism (depth=4): (0, 2, 0, 1, 3) <-> (0, 2, 0, 1)
(0, 2, 0, 1, 3) is reducible to (0, 2, 0, 1)
       	states to check: 3 ,   nodes in tree: 830 ,   states: 5

Checking: (0, 2, 0, 1)
Checking isomorphism (depth=4): (0, 2, 0, 1) <-> (0, 1, 0)
(0, 2, 0, 1) is reducible to (0, 1, 0)
       	states to check: 2 ,   nodes in tree: 830 ,   states: 5

Checking: (0, 1, 0, 2, 0)
(0, 1, 0, 2, 0) is not reducible
       	states to check: 3 ,   nodes in tree: 830 ,   states: 6

Checking: (3, 1, 0, 2, 0)
Checking isomorphism (depth=4): (3, 1, 0, 2, 0) <-> (1, 0, 2, 0)
(3, 1, 0, 2, 0) is reducible to (1, 0, 2, 0)
       	states to check: 3 ,   nodes in tree: 1126 ,   states: 6

Checking: (1, 0, 2, 0)
Checking isomorphism (depth=4): (1, 0, 2, 0) <-> (0, 1, 0)
(1, 0, 2, 0) is reducible to (0, 1, 0)
       	states to check: 2 ,   nodes in tree: 1126 ,   states: 6

Checking: (3, 0, 1, 0, 2, 0)
Checking isomorphism (depth=5): (3, 0, 1, 0, 2, 0) <-> (0, 1, 0, 2, 0)
(3, 0, 1, 0, 2, 0) is reducible to (0, 1, 0, 2, 0)
       	states to check: 1 ,   nodes in tree: 1334 ,   states: 6

Checking: (0, 2, 0, 1, 0, 3)
Checking isomorphism (depth=5): (0, 2, 0, 1, 0, 3) <-> (0, 2, 0, 1, 0)
(0, 2, 0, 1, 0, 3) is reducible to (0, 2, 0, 1, 0)

In [4]: I.gf()
Out[4]: (x**2 - 4*x + 1)/((x - 1)*(4*x - 1))