Testing whether a list of permutations avoids two permutations

savecancel

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.

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)