# Testing whether a list of permutations avoids two permutations

I have a list of $n$-permutations in Sage, for example:

U=[[2, 3, 1, 4, 5], [2, 4, 1, 3, 5], [2, 5, 1, 3, 4], [2, 1, 3, 4, 5], [1, 3, 4, 2, 5], [1, 3, 5, 2, 4], [1, 3, 2, 4, 5], [3, 1, 4, 2, 5], [3, 4, 1, 2, 5], [3, 5, 1, 2, 4], [3, 1, 2, 4, 5], [1, 2, 4, 5, 3], [1, 2, 4, 3, 5], [1, 4, 2, 5, 3], [1, 4, 5, 2, 3], [1, 4, 2, 3, 5], [4, 1, 2, 5, 3], [4, 1, 5, 2, 3], [4, 5, 1, 2, 3], [4, 1, 2, 3, 5], [1, 2, 3, 5, 4], [1, 2, 5, 3, 4], [1, 5, 2, 3, 4], [5, 1, 2, 3, 4], [1, 2, 3, 4, 5]]


Now I want to check whether this lists is in Av($\pi_1,\pi_2$) , the permutations that avoid the two permutations $\pi_1$ and $\pi_2$ when $\pi_1$ and $\pi_2$ are given (or maybe even more than two given permutations).

Is there an easy or even existing way to do this with Sage?

edit retag close merge delete

Sort by » oldest newest most voted

You can use pure Python and avoids (see documentation) for a direct implementation:

sage: P = Permutations(5)
sage: pi_1 = [1, 2, 3, 4, 5]
sage: pi_2 = [4, 1, 2, 3, 5]
sage: all(P(x).avoids(pi_1) and P(x).avoids(pi_2) for x in U)
True/False


As of version 9.4, Sage will support sets with given predicates (see Release Tour), which allows you to define the set $\mathrm{Av}(π_1,π_2)$ directly:

sage: P = Permutations(5)
sage: pi_1 = [1, 2, 3, 4, 5]
sage: pi_2 = [4, 1, 2, 3, 5]
sage: Av = ConditionSet(P, lambda x: x.avoids(pi_1) and x.avoids(pi_2))
sage: all(P(x) in Av for x in U)
True/False


Mathematically, the latter version is a bit nicer, but there is basically no difference.

more

Nice tip about ConditionSet!

( 2021-08-15 15:12:29 +0100 )edit

Say U is a list of permutations and F is a list of forbidden patterns.

We want to check that all permutations in U avoid all forbidden patterns.

One way to perform such a check is as follows:

sage: U = [[2, 3, 1, 4, 5], [2, 4, 1, 3, 5], [2, 5, 1, 3, 4], [2, 1, 3, 4, 5],
....:      [1, 3, 4, 2, 5], [1, 3, 5, 2, 4], [1, 3, 2, 4, 5], [3, 1, 4, 2, 5],
....:      [3, 4, 1, 2, 5], [3, 5, 1, 2, 4], [3, 1, 2, 4, 5], [1, 2, 4, 5, 3],
....:      [1, 2, 4, 3, 5], [1, 4, 2, 5, 3], [1, 4, 5, 2, 3], [1, 4, 2, 3, 5],
....:      [4, 1, 2, 5, 3], [4, 1, 5, 2, 3], [4, 5, 1, 2, 3], [4, 1, 2, 3, 5],
....:      [1, 2, 3, 5, 4], [1, 2, 5, 3, 4], [1, 5, 2, 3, 4], [5, 1, 2, 3, 4],
....:      [1, 2, 3, 4, 5]]
sage: F = [[3, 1, 2, 4], [4, 1, 2, 3]]

sage: U = [Permutation(p) for p in U]
sage: F = [Permutation(p) for p in F]

sage: all(u.avoids(f) for f in F for u in U)

more

Oh, you were faster...

( 2021-08-15 00:15:24 +0100 )edit

Thank you. Is it even possible to input a list of $n$-permutations for (lets say) $n=2,...,7$ and Sage gives a (minimal list) of permutations $\pi_1,..., \pi_r$ such that those permutations are exactly $Av(\pi_1,...,\pi_r)$ until that $n$? This would be very useful to produce some conjectures with the help of Sage.

( 2021-08-15 12:57:13 +0100 )edit