Ask Your Question
1

Testing whether a list of permutations avoids two permutations

asked 2021-08-14 21:21:40 +0200

klaaa gravatar image

updated 2021-08-14 21:21:58 +0200

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 flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted
3

answered 2021-08-15 00:13:31 +0200

mjungmath gravatar image

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.

edit flag offensive delete link more

Comments

Nice tip about ConditionSet!

slelievre gravatar imageslelievre ( 2021-08-15 15:12:29 +0200 )edit
2

answered 2021-08-15 00:01:15 +0200

slelievre gravatar image

updated 2021-08-15 00:10:31 +0200

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)
edit flag offensive delete link more

Comments

Oh, you were faster...

mjungmath gravatar imagemjungmath ( 2021-08-15 00:15:24 +0200 )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.

klaaa gravatar imageklaaa ( 2021-08-15 12:57:13 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-08-14 21:21:40 +0200

Seen: 126 times

Last updated: Aug 15 '21