A bijectionist’s toolkit#
AUTHORS:
Alexander Grosz, Tobias Kietreiber, Stephan Pfannerer and Martin Rubey (2020-2022): Initial version
Quick reference#
Declare statistics that are preserved by the bijection. |
|
Restrict the values of the statistic on an element. |
|
Declare that the statistic is constant on some sets. |
|
Restrict the distribution of values of the statistic on some elements. |
|
Declare that the statistic intertwines with other maps. |
|
Declare that the statistic satisfies a certain relation. |
|
Declare that the statistic is homomesic with respect to a given set partition. |
|
Print a table collecting information on the given statistics. |
|
Collect elements with the same statistics. |
|
Return the blocks on which the statistic is constant. |
|
Iterate over all possible solutions. |
|
Return all possible values for a given element. |
|
Iterate over the minimal subdistributions. |
|
Iterate over the minimal subdistributions. |
A guided tour#
Consider the following combinatorial statistics on a permutation:
\(wex\), the number of weak excedences,
\(fix\), the number of fixed points,
\(des\), the number of descents (after appending \(0\)),
\(adj\), the number of adjacencies (after appending \(0\)), and
\(llis\), the length of a longest increasing subsequence.
Moreover, let \(rot\) be action of rotation on a permutation, i.e., the conjugation with the long cycle.
It is known that there must exist a statistic \(s\) on permutations, which is equidistributed with \(llis\) but additionally invariant under \(rot\). However, at least very small cases do not contradict the possibility that one can even find a statistic \(s\), invariant under \(rot\) and such that \((s, wex, fix) \sim (llis, des, adj)\). Let us check this for permutations of size at most \(3\):
sage: N = 3
sage: A = B = [pi for n in range(N+1) for pi in Permutations(n)]
sage: def alpha1(p): return len(p.weak_excedences())
sage: def alpha2(p): return len(p.fixed_points())
sage: def beta1(p): return len(p.descents(final_descent=True)) if p else 0
sage: def beta2(p): return len([e for (e, f) in zip(p, p[1:]+[0]) if e == f+1])
sage: tau = Permutation.longest_increasing_subsequence_length
sage: def rotate_permutation(p):
....: cycle = Permutation(tuple(range(1, len(p)+1)))
....: return Permutation([cycle.inverse()(p(cycle(i))) for i in range(1, len(p)+1)])
sage: bij = Bijectionist(A, B, tau)
sage: bij.set_statistics((len, len), (alpha1, beta1), (alpha2, beta2))
sage: a, b = bij.statistics_table()
sage: table(a, header_row=True, frame=True)
┌───────────┬────────┬────────┬────────┐
│ a | α_1(a) | α_2(a) | α_3(a) |
╞═══════════╪════════╪════════╪════════╡
│ [] | 0 | 0 | 0 |
├───────────┼────────┼────────┼────────┤
│ [1] | 1 | 1 | 1 |
├───────────┼────────┼────────┼────────┤
│ [1, 2] | 2 | 2 | 2 |
├───────────┼────────┼────────┼────────┤
│ [2, 1] | 2 | 1 | 0 |
├───────────┼────────┼────────┼────────┤
│ [1, 2, 3] | 3 | 3 | 3 |
├───────────┼────────┼────────┼────────┤
│ [1, 3, 2] | 3 | 2 | 1 |
├───────────┼────────┼────────┼────────┤
│ [2, 1, 3] | 3 | 2 | 1 |
├───────────┼────────┼────────┼────────┤
│ [2, 3, 1] | 3 | 2 | 0 |
├───────────┼────────┼────────┼────────┤
│ [3, 1, 2] | 3 | 1 | 0 |
├───────────┼────────┼────────┼────────┤
│ [3, 2, 1] | 3 | 2 | 1 |
└───────────┴────────┴────────┴────────┘
sage: table(b, header_row=True, frame=True)
┌───────────┬───┬────────┬────────┬────────┐
│ b | τ | β_1(b) | β_2(b) | β_3(b) |
╞═══════════╪═══╪════════╪════════╪════════╡
│ [] | 0 | 0 | 0 | 0 |
├───────────┼───┼────────┼────────┼────────┤
│ [1] | 1 | 1 | 1 | 1 |
├───────────┼───┼────────┼────────┼────────┤
│ [1, 2] | 2 | 2 | 1 | 0 |
├───────────┼───┼────────┼────────┼────────┤
│ [2, 1] | 1 | 2 | 2 | 2 |
├───────────┼───┼────────┼────────┼────────┤
│ [1, 2, 3] | 3 | 3 | 1 | 0 |
├───────────┼───┼────────┼────────┼────────┤
│ [1, 3, 2] | 2 | 3 | 2 | 1 |
├───────────┼───┼────────┼────────┼────────┤
│ [2, 1, 3] | 2 | 3 | 2 | 1 |
├───────────┼───┼────────┼────────┼────────┤
│ [2, 3, 1] | 2 | 3 | 2 | 1 |
├───────────┼───┼────────┼────────┼────────┤
│ [3, 1, 2] | 2 | 3 | 2 | 0 |
├───────────┼───┼────────┼────────┼────────┤
│ [3, 2, 1] | 1 | 3 | 3 | 3 |
└───────────┴───┴────────┴────────┴────────┘
sage: from sage.combinat.cyclic_sieving_phenomenon import orbit_decomposition
sage: bij.set_constant_blocks(orbit_decomposition(A, rotate_permutation))
sage: bij.constant_blocks()
{{[1, 3, 2], [2, 1, 3], [3, 2, 1]}}
sage: next(bij.solutions_iterator())
{[]: 0,
[1]: 1,
[1, 2]: 1,
[1, 2, 3]: 1,
[1, 3, 2]: 2,
[2, 1]: 2,
[2, 1, 3]: 2,
[2, 3, 1]: 2,
[3, 1, 2]: 3,
[3, 2, 1]: 2}
>>> from sage.all import *
>>> N = Integer(3)
>>> A = B = [pi for n in range(N+Integer(1)) for pi in Permutations(n)]
>>> def alpha1(p): return len(p.weak_excedences())
>>> def alpha2(p): return len(p.fixed_points())
>>> def beta1(p): return len(p.descents(final_descent=True)) if p else Integer(0)
>>> def beta2(p): return len([e for (e, f) in zip(p, p[Integer(1):]+[Integer(0)]) if e == f+Integer(1)])
>>> tau = Permutation.longest_increasing_subsequence_length
>>> def rotate_permutation(p):
... cycle = Permutation(tuple(range(Integer(1), len(p)+Integer(1))))
... return Permutation([cycle.inverse()(p(cycle(i))) for i in range(Integer(1), len(p)+Integer(1))])
>>> bij = Bijectionist(A, B, tau)
>>> bij.set_statistics((len, len), (alpha1, beta1), (alpha2, beta2))
>>> a, b = bij.statistics_table()
>>> table(a, header_row=True, frame=True)
┌───────────┬────────┬────────┬────────┐
│ a | α_1(a) | α_2(a) | α_3(a) |
╞═══════════╪════════╪════════╪════════╡
│ [] | 0 | 0 | 0 |
├───────────┼────────┼────────┼────────┤
│ [1] | 1 | 1 | 1 |
├───────────┼────────┼────────┼────────┤
│ [1, 2] | 2 | 2 | 2 |
├───────────┼────────┼────────┼────────┤
│ [2, 1] | 2 | 1 | 0 |
├───────────┼────────┼────────┼────────┤
│ [1, 2, 3] | 3 | 3 | 3 |
├───────────┼────────┼────────┼────────┤
│ [1, 3, 2] | 3 | 2 | 1 |
├───────────┼────────┼────────┼────────┤
│ [2, 1, 3] | 3 | 2 | 1 |
├───────────┼────────┼────────┼────────┤
│ [2, 3, 1] | 3 | 2 | 0 |
├───────────┼────────┼────────┼────────┤
│ [3, 1, 2] | 3 | 1 | 0 |
├───────────┼────────┼────────┼────────┤
│ [3, 2, 1] | 3 | 2 | 1 |
└───────────┴────────┴────────┴────────┘
>>> table(b, header_row=True, frame=True)
┌───────────┬───┬────────┬────────┬────────┐
│ b | τ | β_1(b) | β_2(b) | β_3(b) |
╞═══════════╪═══╪════════╪════════╪════════╡
│ [] | 0 | 0 | 0 | 0 |
├───────────┼───┼────────┼────────┼────────┤
│ [1] | 1 | 1 | 1 | 1 |
├───────────┼───┼────────┼────────┼────────┤
│ [1, 2] | 2 | 2 | 1 | 0 |
├───────────┼───┼────────┼────────┼────────┤
│ [2, 1] | 1 | 2 | 2 | 2 |
├───────────┼───┼────────┼────────┼────────┤
│ [1, 2, 3] | 3 | 3 | 1 | 0 |
├───────────┼───┼────────┼────────┼────────┤
│ [1, 3, 2] | 2 | 3 | 2 | 1 |
├───────────┼───┼────────┼────────┼────────┤
│ [2, 1, 3] | 2 | 3 | 2 | 1 |
├───────────┼───┼────────┼────────┼────────┤
│ [2, 3, 1] | 2 | 3 | 2 | 1 |
├───────────┼───┼────────┼────────┼────────┤
│ [3, 1, 2] | 2 | 3 | 2 | 0 |
├───────────┼───┼────────┼────────┼────────┤
│ [3, 2, 1] | 1 | 3 | 3 | 3 |
└───────────┴───┴────────┴────────┴────────┘
>>> from sage.combinat.cyclic_sieving_phenomenon import orbit_decomposition
>>> bij.set_constant_blocks(orbit_decomposition(A, rotate_permutation))
>>> bij.constant_blocks()
{{[1, 3, 2], [2, 1, 3], [3, 2, 1]}}
>>> next(bij.solutions_iterator())
{[]: 0,
[1]: 1,
[1, 2]: 1,
[1, 2, 3]: 1,
[1, 3, 2]: 2,
[2, 1]: 2,
[2, 1, 3]: 2,
[2, 3, 1]: 2,
[3, 1, 2]: 3,
[3, 2, 1]: 2}
On the other hand, we can check that there is no rotation invariant statistic on non-crossing set partitions which is equidistributed with the Strahler number on ordered trees:
sage: N = 8
sage: A = [SetPartition(d.to_noncrossing_partition()) for n in range(N) for d in DyckWords(n)]
sage: B = [t for n in range(1, N+1) for t in OrderedTrees(n)]
sage: def theta(m): return SetPartition([[i % m.size() + 1 for i in b] for b in m])
>>> from sage.all import *
>>> N = Integer(8)
>>> A = [SetPartition(d.to_noncrossing_partition()) for n in range(N) for d in DyckWords(n)]
>>> B = [t for n in range(Integer(1), N+Integer(1)) for t in OrderedTrees(n)]
>>> def theta(m): return SetPartition([[i % m.size() + Integer(1) for i in b] for b in m])
Code for the Strahler number can be obtained from FindStat. The
following code is equivalent to tau = findstat(397):
sage: def tau(T):
....: if len(T) == 0:
....: return 1
....: else:
....: l = [tau(S) for S in T]
....: m = max(l)
....: if l.count(m) == 1:
....: return m
....: else:
....: return m+1
sage: bij = Bijectionist(A, B, tau)
sage: bij.set_statistics((lambda a: a.size(), lambda b: b.node_number()-1))
sage: from sage.combinat.cyclic_sieving_phenomenon import orbit_decomposition
sage: bij.set_constant_blocks(orbit_decomposition(A, theta))
sage: list(bij.solutions_iterator())
[]
>>> from sage.all import *
>>> def tau(T):
... if len(T) == Integer(0):
... return Integer(1)
... else:
... l = [tau(S) for S in T]
... m = max(l)
... if l.count(m) == Integer(1):
... return m
... else:
... return m+Integer(1)
>>> bij = Bijectionist(A, B, tau)
>>> bij.set_statistics((lambda a: a.size(), lambda b: b.node_number()-Integer(1)))
>>> from sage.combinat.cyclic_sieving_phenomenon import orbit_decomposition
>>> bij.set_constant_blocks(orbit_decomposition(A, theta))
>>> list(bij.solutions_iterator())
[]
Next we demonstrate how to search for a bijection, instead An example identifying \(s\) and \(S\):
sage: N = 4
sage: A = [dyck_word for n in range(1, N) for dyck_word in DyckWords(n)]
sage: B = [binary_tree for n in range(1, N) for binary_tree in BinaryTrees(n)]
sage: concat_path = lambda D1, D2: DyckWord(list(D1) + list(D2))
sage: concat_tree = lambda B1, B2: concat_path(B1.to_dyck_word(),
....: B2.to_dyck_word()).to_binary_tree()
sage: bij = Bijectionist(A, B)
sage: bij.set_intertwining_relations((2, concat_path, concat_tree))
sage: bij.set_statistics((lambda d: d.semilength(), lambda t: t.node_number()))
sage: for D in sorted(bij.minimal_subdistributions_iterator(), key=lambda x: (len(x[0][0]), x)):
....: ascii_art(D)
( [ /\ ], [ o ] )
( [ o ] )
( [ \ ] )
( [ /\/\ ], [ o ] )
( [ o ] )
( [ /\ ] [ / ] )
( [ / \ ], [ o ] )
( [ o ] )
( [ \ ] )
( [ o ] )
( [ \ ] )
( [ /\/\/\ ], [ o ] )
( [ o ] )
( [ \ ] )
( [ o ] )
( [ /\ ] [ / ] )
( [ /\/ \ ], [ o ] )
( [ o ] )
( [ /\ ] [ / \ ] )
( [ / \/\ ], [ o o ] )
( [ o, o ] )
( [ / / ] )
( [ /\ ] [ o o ] )
( [ /\/\ / \ ] [ \ / ] )
( [ / \, / \ ], [ o o ] )
>>> from sage.all import *
>>> N = Integer(4)
>>> A = [dyck_word for n in range(Integer(1), N) for dyck_word in DyckWords(n)]
>>> B = [binary_tree for n in range(Integer(1), N) for binary_tree in BinaryTrees(n)]
>>> concat_path = lambda D1, D2: DyckWord(list(D1) + list(D2))
>>> concat_tree = lambda B1, B2: concat_path(B1.to_dyck_word(),
... B2.to_dyck_word()).to_binary_tree()
>>> bij = Bijectionist(A, B)
>>> bij.set_intertwining_relations((Integer(2), concat_path, concat_tree))
>>> bij.set_statistics((lambda d: d.semilength(), lambda t: t.node_number()))
>>> for D in sorted(bij.minimal_subdistributions_iterator(), key=lambda x: (len(x[Integer(0)][Integer(0)]), x)):
... ascii_art(D)
( [ /\ ], [ o ] )
( [ o ] )
( [ \ ] )
( [ /\/\ ], [ o ] )
( [ o ] )
( [ /\ ] [ / ] )
( [ / \ ], [ o ] )
( [ o ] )
( [ \ ] )
( [ o ] )
( [ \ ] )
( [ /\/\/\ ], [ o ] )
( [ o ] )
( [ \ ] )
( [ o ] )
( [ /\ ] [ / ] )
( [ /\/ \ ], [ o ] )
( [ o ] )
( [ /\ ] [ / \ ] )
( [ / \/\ ], [ o o ] )
( [ o, o ] )
( [ / / ] )
( [ /\ ] [ o o ] )
( [ /\/\ / \ ] [ \ / ] )
( [ / \, / \ ], [ o o ] )
The output is in a form suitable for FindStat:
sage: findmap(list(bij.minimal_subdistributions_iterator())) # optional -- internet
0: Mp00034 (quality [100])
1: Mp00061oMp00023 (quality [100])
2: Mp00018oMp00140 (quality [100])
>>> from sage.all import *
>>> findmap(list(bij.minimal_subdistributions_iterator())) # optional -- internet
0: Mp00034 (quality [100])
1: Mp00061oMp00023 (quality [100])
2: Mp00018oMp00140 (quality [100])
- class sage.combinat.bijectionist.Bijectionist(A, B, tau=None, alpha_beta=(), P=None, pi_rho=(), phi_psi=(), Q=None, elements_distributions=(), value_restrictions=(), solver=None, key=None)[source]#
Bases:
SageObjectA toolbox to list all possible bijections between two finite sets under various constraints.
INPUT:
A,B– sets of equal size, given as a listtau– (optional) a function fromBtoZ, in case ofNone, the identity maplambda x: xis usedalpha_beta– (optional) a list of pairs of statisticsalphafromAtoWandbetafromBtoWP– (optional) a partition ofApi_rho– (optional) a list of triples(k, pi, rho), wherepi– ak-ary operation composing objects inAandrho– ak-ary function composing statistic values inZ
elements_distributions– (optional) a list of pairs(tA, tZ), specifying the distributions oftAvalue_restrictions– (optional) a list of pairs(a, tZ), restricting the possible values ofasolver– (optional) the backend used to solve the mixed integer linear programs
WandZcan be arbitrary sets. As a natural example we may think of the natural numbers or tuples of integers.We are looking for a statistic \(s: A\to Z\) and a bijection \(S: A\to B\) such that
\(s = \tau \circ S\): the statistics \(s\) and \(\tau\) are equidistributed and \(S\) is an intertwining bijection.
\(\alpha = \beta \circ S\): the statistics \(\alpha\) and \(\beta\) are equidistributed and \(S\) is an intertwining bijection.
\(s\) is constant on the blocks of \(P\).
\(s(\pi(a_1,\dots, a_k)) = \rho(s(a_1),\dots, s(a_k))\).
Additionally, we may require that
\(s(a)\in Z_a\) for specified sets \(Z_a\subseteq Z\), and
\(s|_{\tilde A}\) has a specified distribution for specified sets \(\tilde A \subset A\).
If \(\tau\) is the identity, the two unknown functions \(s\) and \(S\) coincide. Although we do not exclude other bijective choices for \(\tau\), they probably do not make sense.
If we want that \(S\) is graded, i.e. if elements of \(A\) and \(B\) have a notion of size and \(S\) should preserve this size, we can add grading statistics as \(\alpha\) and \(\beta\). Since \(\alpha\) and \(\beta\) will be equidistributed with \(S\) as an intertwining bijection, \(S\) will then also be graded.
In summary, we have the following two commutative diagrams, where \(s\) and \(S\) are unknown functions.
\[\begin{split}\begin{array}{rrl} & A \\ {\scriptstyle\alpha}\swarrow & {\scriptstyle S}\downarrow & \searrow{\scriptstyle s}\\ W \overset{\beta}{\leftarrow} & B & \overset{\tau}{\rightarrow} Z \end{array} \qquad \begin{array}{lcl} A^k &\overset{\pi}{\rightarrow} & A\\ \downarrow{\scriptstyle s^k} & & \downarrow{\scriptstyle s}\\ Z^k &\overset{\rho}{\rightarrow} & Z\\ \end{array}\end{split}\]Note
If \(\tau\) is the identity map, the partition \(P\) of \(A\) necessarily consists only of singletons.
Note
The order of invocation of the methods with prefix
set, i.e.,set_statistics(),set_intertwining_relations(),set_constant_blocks(), etc., is irrelevant. Calling any of these methods a second time overrides the previous specification.- constant_blocks(singletons=False, optimal=False)[source]#
Return the set partition \(P\) of \(A\) such that \(s: A\to Z\) is known to be constant on the blocks of \(P\).
INPUT:
singletons– (default:False) whether or not to include singleton blocks in the outputoptimal– (default:False) whether or not to compute the coarsest possible partition
Note
computing the coarsest possible partition may be computationally expensive, but may speed up generating solutions.
EXAMPLES:
sage: A = B = ["a", "b", "c"] sage: bij = Bijectionist(A, B, lambda x: 0) sage: bij.set_constant_blocks([["a", "b"]]) sage: bij.constant_blocks() {{'a', 'b'}} sage: bij.constant_blocks(singletons=True) {{'a', 'b'}, {'c'}}
>>> from sage.all import * >>> A = B = ["a", "b", "c"] >>> bij = Bijectionist(A, B, lambda x: Integer(0)) >>> bij.set_constant_blocks([["a", "b"]]) >>> bij.constant_blocks() {{'a', 'b'}} >>> bij.constant_blocks(singletons=True) {{'a', 'b'}, {'c'}}
- minimal_subdistributions_blocks_iterator()[source]#
Return all representatives of minimal subsets \(\tilde P\) of \(P\) together with submultisets \(\tilde Z\) with \(s(\tilde P) = \tilde Z\) as multisets.
Warning
If there are several solutions with the same support (i.e., the sets of block representatives are the same), only one of these will be found, even if the distributions are different, see the doctest below. To find all solutions, use
minimal_subdistributions_iterator(), which is, however, computationally more expensive.EXAMPLES:
sage: A = B = [permutation for n in range(3) for permutation in Permutations(n)] sage: bij = Bijectionist(A, B, len) sage: bij.set_statistics((len, len)) sage: for sol in bij.solutions_iterator(): ....: print(sol) {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 2} sage: sorted(bij.minimal_subdistributions_blocks_iterator()) [([[]], [0]), ([[1]], [1]), ([[1, 2]], [2]), ([[2, 1]], [2])]
>>> from sage.all import * >>> A = B = [permutation for n in range(Integer(3)) for permutation in Permutations(n)] >>> bij = Bijectionist(A, B, len) >>> bij.set_statistics((len, len)) >>> for sol in bij.solutions_iterator(): ... print(sol) {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 2} >>> sorted(bij.minimal_subdistributions_blocks_iterator()) [([[]], [0]), ([[1]], [1]), ([[1, 2]], [2]), ([[2, 1]], [2])]
Another example:
sage: N = 2; A = B = [dyck_word for n in range(N+1) for dyck_word in DyckWords(n)] sage: def tau(D): return D.number_of_touch_points() sage: bij = Bijectionist(A, B, tau) sage: bij.set_statistics((lambda d: d.semilength(), lambda d: d.semilength())) sage: for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ....: print(solution) {[]: 0, [1, 0]: 1, [1, 0, 1, 0]: 1, [1, 1, 0, 0]: 2} {[]: 0, [1, 0]: 1, [1, 0, 1, 0]: 2, [1, 1, 0, 0]: 1} sage: for subdistribution in bij.minimal_subdistributions_blocks_iterator(): ....: print(subdistribution) ([[]], [0]) ([[1, 0]], [1]) ([[1, 0, 1, 0], [1, 1, 0, 0]], [1, 2])
>>> from sage.all import * >>> N = Integer(2); A = B = [dyck_word for n in range(N+Integer(1)) for dyck_word in DyckWords(n)] >>> def tau(D): return D.number_of_touch_points() >>> bij = Bijectionist(A, B, tau) >>> bij.set_statistics((lambda d: d.semilength(), lambda d: d.semilength())) >>> for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ... print(solution) {[]: 0, [1, 0]: 1, [1, 0, 1, 0]: 1, [1, 1, 0, 0]: 2} {[]: 0, [1, 0]: 1, [1, 0, 1, 0]: 2, [1, 1, 0, 0]: 1} >>> for subdistribution in bij.minimal_subdistributions_blocks_iterator(): ... print(subdistribution) ([[]], [0]) ([[1, 0]], [1]) ([[1, 0, 1, 0], [1, 1, 0, 0]], [1, 2])
An example with two elements of the same block in a subdistribution:
sage: A = B = ["a", "b", "c", "d", "e"] sage: tau = {"a": 1, "b": 1, "c": 2, "d": 2, "e": 3}.get sage: bij = Bijectionist(A, B, tau) sage: bij.set_constant_blocks([["a", "b"]]) sage: bij.set_value_restrictions(("a", [1, 2])) sage: bij.constant_blocks(optimal=True) {{'a', 'b'}} sage: list(bij.minimal_subdistributions_blocks_iterator()) [(['b', 'b', 'c', 'd', 'e'], [1, 1, 2, 2, 3])]
>>> from sage.all import * >>> A = B = ["a", "b", "c", "d", "e"] >>> tau = {"a": Integer(1), "b": Integer(1), "c": Integer(2), "d": Integer(2), "e": Integer(3)}.get >>> bij = Bijectionist(A, B, tau) >>> bij.set_constant_blocks([["a", "b"]]) >>> bij.set_value_restrictions(("a", [Integer(1), Integer(2)])) >>> bij.constant_blocks(optimal=True) {{'a', 'b'}} >>> list(bij.minimal_subdistributions_blocks_iterator()) [(['b', 'b', 'c', 'd', 'e'], [1, 1, 2, 2, 3])]
An example with overlapping minimal subdistributions:
sage: A = B = ["a", "b", "c", "d", "e"] sage: tau = {"a": 1, "b": 1, "c": 2, "d": 2, "e": 3}.get sage: bij = Bijectionist(A, B, tau) sage: bij.set_distributions((["a", "b"], [1, 2]), (["a", "c", "d"], [1, 2, 3])) sage: sorted(bij.solutions_iterator(), key=lambda d: tuple(sorted(d.items()))) [{'a': 1, 'b': 2, 'c': 2, 'd': 3, 'e': 1}, {'a': 1, 'b': 2, 'c': 3, 'd': 2, 'e': 1}, {'a': 2, 'b': 1, 'c': 1, 'd': 3, 'e': 2}, {'a': 2, 'b': 1, 'c': 3, 'd': 1, 'e': 2}] sage: bij.constant_blocks(optimal=True) {{'a', 'e'}} sage: list(bij.minimal_subdistributions_blocks_iterator()) [(['a', 'b'], [1, 2]), (['a', 'c', 'd'], [1, 2, 3])]
>>> from sage.all import * >>> A = B = ["a", "b", "c", "d", "e"] >>> tau = {"a": Integer(1), "b": Integer(1), "c": Integer(2), "d": Integer(2), "e": Integer(3)}.get >>> bij = Bijectionist(A, B, tau) >>> bij.set_distributions((["a", "b"], [Integer(1), Integer(2)]), (["a", "c", "d"], [Integer(1), Integer(2), Integer(3)])) >>> sorted(bij.solutions_iterator(), key=lambda d: tuple(sorted(d.items()))) [{'a': 1, 'b': 2, 'c': 2, 'd': 3, 'e': 1}, {'a': 1, 'b': 2, 'c': 3, 'd': 2, 'e': 1}, {'a': 2, 'b': 1, 'c': 1, 'd': 3, 'e': 2}, {'a': 2, 'b': 1, 'c': 3, 'd': 1, 'e': 2}] >>> bij.constant_blocks(optimal=True) {{'a', 'e'}} >>> list(bij.minimal_subdistributions_blocks_iterator()) [(['a', 'b'], [1, 2]), (['a', 'c', 'd'], [1, 2, 3])]
Fedor Petrov’s example from https://mathoverflow.net/q/424187:
sage: A = B = ["a"+str(i) for i in range(1, 9)] + ["b"+str(i) for i in range(3, 9)] + ["d"] sage: tau = {b: 0 if i < 10 else 1 for i, b in enumerate(B)}.get sage: bij = Bijectionist(A, B, tau) sage: bij.set_constant_blocks([["a"+str(i), "b"+str(i)] for i in range(1, 9) if "b"+str(i) in A]) sage: d = [0]*8+[1]*4 sage: bij.set_distributions((A[:8] + A[8+2:-1], d), (A[:8] + A[8:-3], d)) sage: sorted([s[a] for a in A] for s in bij.solutions_iterator()) [[0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1], [0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0], [0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0], [0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0], [0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0], [1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0], [1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0], [1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0], [1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1], [1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]] sage: sorted(bij.minimal_subdistributions_blocks_iterator()) # random [(['a1', 'a2', 'a3', 'a4', 'a5', 'a5', 'a6', 'a6', 'a7', 'a7', 'a8', 'a8'], [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1]), (['a3', 'a4', 'd'], [0, 0, 1]), (['a7', 'a8', 'd'], [0, 0, 1])]
>>> from sage.all import * >>> A = B = ["a"+str(i) for i in range(Integer(1), Integer(9))] + ["b"+str(i) for i in range(Integer(3), Integer(9))] + ["d"] >>> tau = {b: Integer(0) if i < Integer(10) else Integer(1) for i, b in enumerate(B)}.get >>> bij = Bijectionist(A, B, tau) >>> bij.set_constant_blocks([["a"+str(i), "b"+str(i)] for i in range(Integer(1), Integer(9)) if "b"+str(i) in A]) >>> d = [Integer(0)]*Integer(8)+[Integer(1)]*Integer(4) >>> bij.set_distributions((A[:Integer(8)] + A[Integer(8)+Integer(2):-Integer(1)], d), (A[:Integer(8)] + A[Integer(8):-Integer(3)], d)) >>> sorted([s[a] for a in A] for s in bij.solutions_iterator()) [[0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1], [0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0], [0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0], [0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0], [0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0], [1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0], [1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0], [1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0], [1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1], [1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]] >>> sorted(bij.minimal_subdistributions_blocks_iterator()) # random [(['a1', 'a2', 'a3', 'a4', 'a5', 'a5', 'a6', 'a6', 'a7', 'a7', 'a8', 'a8'], [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1]), (['a3', 'a4', 'd'], [0, 0, 1]), (['a7', 'a8', 'd'], [0, 0, 1])]
The following solution is not found, because it happens to have the same support as the other:
sage: D = set(A).difference(['b7', 'b8', 'd']) sage: sorted(a.replace("b", "a") for a in D) ['a1', 'a2', 'a3', 'a3', 'a4', 'a4', 'a5', 'a5', 'a6', 'a6', 'a7', 'a8'] sage: set(tuple(sorted(s[a] for a in D)) for s in bij.solutions_iterator()) {(0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1)}
>>> from sage.all import * >>> D = set(A).difference(['b7', 'b8', 'd']) >>> sorted(a.replace("b", "a") for a in D) ['a1', 'a2', 'a3', 'a3', 'a4', 'a4', 'a5', 'a5', 'a6', 'a6', 'a7', 'a8'] >>> set(tuple(sorted(s[a] for a in D)) for s in bij.solutions_iterator()) {(0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1)}
But it is, by design, included here:
sage: sorted(D) in [d for d, _ in bij.minimal_subdistributions_iterator()] True
>>> from sage.all import * >>> sorted(D) in [d for d, _ in bij.minimal_subdistributions_iterator()] True
- minimal_subdistributions_iterator()[source]#
Return all minimal subsets \(\tilde A\) of \(A\) together with submultisets \(\tilde Z\) with \(s(\tilde A) = \tilde Z\) as multisets.
EXAMPLES:
sage: A = B = [permutation for n in range(3) for permutation in Permutations(n)] sage: bij = Bijectionist(A, B, len) sage: bij.set_statistics((len, len)) sage: for sol in bij.solutions_iterator(): ....: print(sol) {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 2} sage: sorted(bij.minimal_subdistributions_iterator()) [([[]], [0]), ([[1]], [1]), ([[1, 2]], [2]), ([[2, 1]], [2])]
>>> from sage.all import * >>> A = B = [permutation for n in range(Integer(3)) for permutation in Permutations(n)] >>> bij = Bijectionist(A, B, len) >>> bij.set_statistics((len, len)) >>> for sol in bij.solutions_iterator(): ... print(sol) {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 2} >>> sorted(bij.minimal_subdistributions_iterator()) [([[]], [0]), ([[1]], [1]), ([[1, 2]], [2]), ([[2, 1]], [2])]
Another example:
sage: N = 2; A = B = [dyck_word for n in range(N+1) for dyck_word in DyckWords(n)] sage: def tau(D): return D.number_of_touch_points() sage: bij = Bijectionist(A, B, tau) sage: bij.set_statistics((lambda d: d.semilength(), lambda d: d.semilength())) sage: for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ....: print(solution) {[]: 0, [1, 0]: 1, [1, 0, 1, 0]: 1, [1, 1, 0, 0]: 2} {[]: 0, [1, 0]: 1, [1, 0, 1, 0]: 2, [1, 1, 0, 0]: 1} sage: for subdistribution in bij.minimal_subdistributions_iterator(): ....: print(subdistribution) ([[]], [0]) ([[1, 0]], [1]) ([[1, 0, 1, 0], [1, 1, 0, 0]], [1, 2])
>>> from sage.all import * >>> N = Integer(2); A = B = [dyck_word for n in range(N+Integer(1)) for dyck_word in DyckWords(n)] >>> def tau(D): return D.number_of_touch_points() >>> bij = Bijectionist(A, B, tau) >>> bij.set_statistics((lambda d: d.semilength(), lambda d: d.semilength())) >>> for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ... print(solution) {[]: 0, [1, 0]: 1, [1, 0, 1, 0]: 1, [1, 1, 0, 0]: 2} {[]: 0, [1, 0]: 1, [1, 0, 1, 0]: 2, [1, 1, 0, 0]: 1} >>> for subdistribution in bij.minimal_subdistributions_iterator(): ... print(subdistribution) ([[]], [0]) ([[1, 0]], [1]) ([[1, 0, 1, 0], [1, 1, 0, 0]], [1, 2])
An example with two elements of the same block in a subdistribution:
sage: A = B = ["a", "b", "c", "d", "e"] sage: tau = {"a": 1, "b": 1, "c": 2, "d": 2, "e": 3}.get sage: bij = Bijectionist(A, B, tau) sage: bij.set_constant_blocks([["a", "b"]]) sage: bij.set_value_restrictions(("a", [1, 2])) sage: bij.constant_blocks(optimal=True) {{'a', 'b'}} sage: list(bij.minimal_subdistributions_iterator()) [(['a', 'b', 'c', 'd', 'e'], [1, 1, 2, 2, 3])]
>>> from sage.all import * >>> A = B = ["a", "b", "c", "d", "e"] >>> tau = {"a": Integer(1), "b": Integer(1), "c": Integer(2), "d": Integer(2), "e": Integer(3)}.get >>> bij = Bijectionist(A, B, tau) >>> bij.set_constant_blocks([["a", "b"]]) >>> bij.set_value_restrictions(("a", [Integer(1), Integer(2)])) >>> bij.constant_blocks(optimal=True) {{'a', 'b'}} >>> list(bij.minimal_subdistributions_iterator()) [(['a', 'b', 'c', 'd', 'e'], [1, 1, 2, 2, 3])]
- possible_values(p=None, optimal=False)[source]#
Return for each block the values of \(s\) compatible with the imposed restrictions.
INPUT:
p– (optional) a block of \(P\), or an element of a block of \(P\), or a list of theseoptimal– (default:False) whether or not to compute the minimal possible set of statistic values
Note
Computing the minimal possible set of statistic values may be computationally expensive.
Todo
currently, calling this method with
optimal=Truedoes not update the internal dictionary, because this would interfere with the variables of the MILP.EXAMPLES:
sage: A = B = ["a", "b", "c", "d"] sage: tau = {"a": 1, "b": 1, "c": 1, "d": 2}.get sage: bij = Bijectionist(A, B, tau) sage: bij.set_constant_blocks([["a", "b"]]) sage: bij.possible_values(A) {'a': {1, 2}, 'b': {1, 2}, 'c': {1, 2}, 'd': {1, 2}} sage: bij.possible_values(A, optimal=True) {'a': {1}, 'b': {1}, 'c': {1, 2}, 'd': {1, 2}}
>>> from sage.all import * >>> A = B = ["a", "b", "c", "d"] >>> tau = {"a": Integer(1), "b": Integer(1), "c": Integer(1), "d": Integer(2)}.get >>> bij = Bijectionist(A, B, tau) >>> bij.set_constant_blocks([["a", "b"]]) >>> bij.possible_values(A) {'a': {1, 2}, 'b': {1, 2}, 'c': {1, 2}, 'd': {1, 2}} >>> bij.possible_values(A, optimal=True) {'a': {1}, 'b': {1}, 'c': {1, 2}, 'd': {1, 2}}
The internal dictionary is not updated:
sage: bij.possible_values(A) {'a': {1, 2}, 'b': {1, 2}, 'c': {1, 2}, 'd': {1, 2}}
>>> from sage.all import * >>> bij.possible_values(A) {'a': {1, 2}, 'b': {1, 2}, 'c': {1, 2}, 'd': {1, 2}}
- set_constant_blocks(P)[source]#
Declare that \(s: A\to Z\) is constant on each block of \(P\).
Warning
Any restriction imposed by a previous invocation of
set_constant_blocks()will be overwritten, including restrictions discovered byset_intertwining_relations()andsolutions_iterator()!A common example is to use the orbits of a bijection acting on \(A\). This can be achieved using the function
orbit_decomposition().INPUT:
P– a set partition of \(A\), singletons may be omitted
EXAMPLES:
Initially the partitions are set to singleton blocks. The current partition can be reviewed using
constant_blocks():sage: A = B = 'abcd' sage: bij = Bijectionist(A, B, lambda x: B.index(x) % 2) sage: bij.constant_blocks() {} sage: bij.set_constant_blocks([['a', 'c']]) sage: bij.constant_blocks() {{'a', 'c'}}
>>> from sage.all import * >>> A = B = 'abcd' >>> bij = Bijectionist(A, B, lambda x: B.index(x) % Integer(2)) >>> bij.constant_blocks() {} >>> bij.set_constant_blocks([['a', 'c']]) >>> bij.constant_blocks() {{'a', 'c'}}
We now add a map that combines some blocks:
sage: def pi(p1, p2): return 'abcdefgh'[A.index(p1) + A.index(p2)] sage: def rho(s1, s2): return (s1 + s2) % 2 sage: bij.set_intertwining_relations((2, pi, rho)) sage: list(bij.solutions_iterator()) [{'a': 0, 'b': 1, 'c': 0, 'd': 1}] sage: bij.constant_blocks() {{'a', 'c'}, {'b', 'd'}}
>>> from sage.all import * >>> def pi(p1, p2): return 'abcdefgh'[A.index(p1) + A.index(p2)] >>> def rho(s1, s2): return (s1 + s2) % Integer(2) >>> bij.set_intertwining_relations((Integer(2), pi, rho)) >>> list(bij.solutions_iterator()) [{'a': 0, 'b': 1, 'c': 0, 'd': 1}] >>> bij.constant_blocks() {{'a', 'c'}, {'b', 'd'}}
Setting constant blocks overrides any previous assignment:
sage: bij.set_constant_blocks([['a', 'b']]) sage: bij.constant_blocks() {{'a', 'b'}}
>>> from sage.all import * >>> bij.set_constant_blocks([['a', 'b']]) >>> bij.constant_blocks() {{'a', 'b'}}
If there is no solution, and the coarsest partition is requested, an error is raised:
sage: bij.constant_blocks(optimal=True) Traceback (most recent call last): ... StopIteration
>>> from sage.all import * >>> bij.constant_blocks(optimal=True) Traceback (most recent call last): ... StopIteration
- set_distributions(*elements_distributions)[source]#
Specify the distribution of \(s\) for a subset of elements.
Warning
Any restriction imposed by a previous invocation of
set_distributions()will be overwritten!INPUT:
one or more pairs of \((\tilde A, \tilde Z)\), where \(\tilde A\subseteq A\) and \(\tilde Z\) is a list of values in \(Z\) of the same size as \(\tilde A\)
This method specifies that \(\{s(a) | a\in\tilde A\}\) equals \(\tilde Z\) as a multiset for each of the pairs.
When specifying several distributions, the subsets of \(A\) do not have to be disjoint.
ALGORITHM:
We add
\[\sum_{a\in\tilde A} x_{p(a), z}t^z = \sum_{z\in\tilde Z} t^z,\]where \(p(a)\) is the block containing \(a\), for each given distribution as a vector equation to the MILP.
EXAMPLES:
sage: A = B = [permutation for n in range(4) for permutation in Permutations(n)] sage: tau = Permutation.longest_increasing_subsequence_length sage: bij = Bijectionist(A, B, tau) sage: bij.set_statistics((len, len)) sage: bij.set_distributions(([Permutation([1, 2, 3]), Permutation([1, 3, 2])], [1, 3])) sage: for sol in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ....: print(sol) {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 3, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 1, [1, 2, 3]: 1, [1, 3, 2]: 3, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 1, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} sage: bij.constant_blocks(optimal=True) {{[2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]}} sage: sorted(bij.minimal_subdistributions_blocks_iterator(), key=lambda d: (len(d[0]), d[0])) [([[]], [0]), ([[1]], [1]), ([[2, 1, 3]], [2]), ([[1, 2], [2, 1]], [1, 2]), ([[1, 2, 3], [1, 3, 2]], [1, 3])]
>>> from sage.all import * >>> A = B = [permutation for n in range(Integer(4)) for permutation in Permutations(n)] >>> tau = Permutation.longest_increasing_subsequence_length >>> bij = Bijectionist(A, B, tau) >>> bij.set_statistics((len, len)) >>> bij.set_distributions(([Permutation([Integer(1), Integer(2), Integer(3)]), Permutation([Integer(1), Integer(3), Integer(2)])], [Integer(1), Integer(3)])) >>> for sol in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ... print(sol) {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 3, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 1, [1, 2, 3]: 1, [1, 3, 2]: 3, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 1, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} >>> bij.constant_blocks(optimal=True) {{[2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]}} >>> sorted(bij.minimal_subdistributions_blocks_iterator(), key=lambda d: (len(d[Integer(0)]), d[Integer(0)])) [([[]], [0]), ([[1]], [1]), ([[2, 1, 3]], [2]), ([[1, 2], [2, 1]], [1, 2]), ([[1, 2, 3], [1, 3, 2]], [1, 3])]
We may also specify multiple, possibly overlapping distributions:
sage: bij.set_distributions(([Permutation([1, 2, 3]), Permutation([1, 3, 2])], [1, 3]), ....: ([Permutation([1, 3, 2]), Permutation([3, 2, 1]), ....: Permutation([2, 1, 3])], [1, 2, 2])) sage: for sol in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ....: print(sol) {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 1, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} sage: bij.constant_blocks(optimal=True) {{[1], [1, 3, 2]}, {[2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]}} sage: sorted(bij.minimal_subdistributions_blocks_iterator(), key=lambda d: (len(d[0]), d[0])) [([[]], [0]), ([[1]], [1]), ([[1, 2, 3]], [3]), ([[2, 3, 1]], [2]), ([[1, 2], [2, 1]], [1, 2])]
>>> from sage.all import * >>> bij.set_distributions(([Permutation([Integer(1), Integer(2), Integer(3)]), Permutation([Integer(1), Integer(3), Integer(2)])], [Integer(1), Integer(3)]), ... ([Permutation([Integer(1), Integer(3), Integer(2)]), Permutation([Integer(3), Integer(2), Integer(1)]), ... Permutation([Integer(2), Integer(1), Integer(3)])], [Integer(1), Integer(2), Integer(2)])) >>> for sol in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ... print(sol) {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 1, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} >>> bij.constant_blocks(optimal=True) {{[1], [1, 3, 2]}, {[2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]}} >>> sorted(bij.minimal_subdistributions_blocks_iterator(), key=lambda d: (len(d[Integer(0)]), d[Integer(0)])) [([[]], [0]), ([[1]], [1]), ([[1, 2, 3]], [3]), ([[2, 3, 1]], [2]), ([[1, 2], [2, 1]], [1, 2])]
- set_homomesic(Q)[source]#
Assert that the average of \(s\) on each block of \(Q\) is constant.
INPUT:
Q– a set partition ofA
EXAMPLES:
sage: A = B = [1,2,3] sage: bij = Bijectionist(A, B, lambda b: b % 3) sage: bij.set_homomesic([[1,2], [3]]) sage: list(bij.solutions_iterator()) [{1: 2, 2: 0, 3: 1}, {1: 0, 2: 2, 3: 1}]
>>> from sage.all import * >>> A = B = [Integer(1),Integer(2),Integer(3)] >>> bij = Bijectionist(A, B, lambda b: b % Integer(3)) >>> bij.set_homomesic([[Integer(1),Integer(2)], [Integer(3)]]) >>> list(bij.solutions_iterator()) [{1: 2, 2: 0, 3: 1}, {1: 0, 2: 2, 3: 1}]
- set_intertwining_relations(*pi_rho)[source]#
Add restrictions of the form \(s(\pi(a_1,\dots, a_k)) = \rho(s(a_1),\dots, s(a_k))\).
Warning
Any restriction imposed by a previous invocation of
set_intertwining_relations()will be overwritten!INPUT:
pi_rho– one or more tuples \((k, \pi: A^k\to A, \rho: Z^k\to Z, \tilde A)\) where \(\tilde A\) (optional) is a \(k\)-ary function that returns true if and only if a \(k\)-tuple of objects in \(A\) is in the domain of \(\pi\)
ALGORITHM:
The relation
\[s(\pi(a_1,\dots, a_k)) = \rho(s(a_1),\dots, s(a_k))\]for each pair \((\pi, \rho)\) implies immediately that \(s(\pi(a_1,\dots, a_k))\) only depends on the blocks of \(a_1,\dots, a_k\).
The MILP formulation is as follows. Let \(a_1,\dots,a_k \in A\) and let \(a = \pi(a_1,\dots,a_k)\). Let \(z_1,\dots,z_k \in Z\) and let \(z = \rho(z_1,\dots,z_k)\). Suppose that \(a_i\in p_i\) for all \(i\) and that \(a\in p\).
We then want to model the implication
\[x_{p_1, z_1} = 1,\dots, x_{p_k, z_k} = 1 \Rightarrow x_{p, z} = 1.\]We achieve this by requiring
\[x_{p, z}\geq 1 - k + \sum_{i=1}^k x_{p_i, z_i}.\]Note that \(z\) must be a possible value of \(p\) and each \(z_i\) must be a possible value of \(p_i\).
EXAMPLES:
We can concatenate two permutations by increasing the values of the second permutation by the length of the first permutation:
sage: def concat(p1, p2): return Permutation(p1 + [i + len(p1) for i in p2])
>>> from sage.all import * >>> def concat(p1, p2): return Permutation(p1 + [i + len(p1) for i in p2])
We may be interested in statistics on permutations which are equidistributed with the number of fixed points, such that concatenating permutations corresponds to adding statistic values:
sage: A = B = [permutation for n in range(4) for permutation in Permutations(n)] sage: bij = Bijectionist(A, B, Permutation.number_of_fixed_points) sage: bij.set_statistics((len, len)) sage: for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ....: print(solution) ... {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3} ... {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 1, [2, 1, 3]: 3, [2, 3, 1]: 0, [3, 1, 2]: 0, [3, 2, 1]: 1} ... sage: bij.set_intertwining_relations((2, concat, lambda x, y: x + y)) sage: for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ....: print(solution) {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 0}
>>> from sage.all import * >>> A = B = [permutation for n in range(Integer(4)) for permutation in Permutations(n)] >>> bij = Bijectionist(A, B, Permutation.number_of_fixed_points) >>> bij.set_statistics((len, len)) >>> for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ... print(solution) ... {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3} ... {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 1, [2, 1, 3]: 3, [2, 3, 1]: 0, [3, 1, 2]: 0, [3, 2, 1]: 1} ... >>> bij.set_intertwining_relations((Integer(2), concat, lambda x, y: x + y)) >>> for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ... print(solution) {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 0}
The domain of the composition may be restricted. E.g., if we concatenate only permutations starting with a 1, we obtain fewer forced elements:
sage: in_domain = lambda p1, p2: (not p1 or p1(1) == 1) and (not p2 or p2(1) == 1) sage: bij.set_intertwining_relations((2, concat, lambda x, y: x + y, in_domain)) sage: for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ....: print(solution) {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 0}
>>> from sage.all import * >>> in_domain = lambda p1, p2: (not p1 or p1(Integer(1)) == Integer(1)) and (not p2 or p2(Integer(1)) == Integer(1)) >>> bij.set_intertwining_relations((Integer(2), concat, lambda x, y: x + y, in_domain)) >>> for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ... print(solution) {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 0}
We can also restrict according to several composition functions. For example, we may additionally concatenate permutations by incrementing the elements of the first:
sage: skew_concat = lambda p1, p2: Permutation([i + len(p2) for i in p1] + list(p2)) sage: bij.set_intertwining_relations((2, skew_concat, lambda x, y: x + y)) sage: for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ....: print(solution) {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 0, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 0, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3}
>>> from sage.all import * >>> skew_concat = lambda p1, p2: Permutation([i + len(p2) for i in p1] + list(p2)) >>> bij.set_intertwining_relations((Integer(2), skew_concat, lambda x, y: x + y)) >>> for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ... print(solution) {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 0, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 0, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3}
However, this yields no solution:
sage: bij.set_intertwining_relations((2, concat, lambda x, y: x + y), (2, skew_concat, lambda x, y: x + y)) sage: list(bij.solutions_iterator()) []
>>> from sage.all import * >>> bij.set_intertwining_relations((Integer(2), concat, lambda x, y: x + y), (Integer(2), skew_concat, lambda x, y: x + y)) >>> list(bij.solutions_iterator()) []
- set_quadratic_relation(*phi_psi)[source]#
Add restrictions of the form \(s\circ\psi\circ s = \phi\).
INPUT:
phi_psi– (optional) a list of pairs \((\phi, \rho)\) where \(\phi: A\to Z\) and \(\psi: Z\to A\)
ALGORITHM:
We add
\[x_{p(a), z} = x_{p(\psi(z)), \phi(a)}\]for \(a\in A\) and \(z\in Z\) to the MILP, where \(\phi:A\to Z\) and \(\psi:Z\to A\). Note that, in particular, \(\phi\) must be constant on blocks.
EXAMPLES:
sage: A = B = DyckWords(3) sage: bij = Bijectionist(A, B) sage: bij.set_statistics((lambda D: D.number_of_touch_points(), lambda D: D.number_of_initial_rises())) sage: ascii_art(sorted(bij.minimal_subdistributions_iterator())) [ ( [ /\ ] ) [ ( [ / \ ] ) ( [ /\ /\ ] [ /\ /\/\ ] ) [ ( [ /\/\/\ ], [ / \ ] ), ( [ /\/ \, / \/\ ], [ / \/\, / \ ] ), ( [ /\ ] ) ] ( [ /\/\ / \ ] [ /\ ] ) ] ( [ / \, / \ ], [ /\/\/\, /\/ \ ] ) ] sage: bij.set_quadratic_relation((lambda D: D, lambda D: D)) sage: ascii_art(sorted(bij.minimal_subdistributions_iterator())) [ ( [ /\ ] ) [ ( [ / \ ] ) ( [ /\ ] [ /\/\ ] ) [ ( [ /\/\/\ ], [ / \ ] ), ( [ /\/ \ ], [ / \ ] ), ( [ /\ ] [ /\ ] ) ( [ /\/\ ] [ /\ ] ) ( [ / \/\ ], [ / \/\ ] ), ( [ / \ ], [ /\/ \ ] ), ( [ /\ ] ) ] ( [ / \ ] ) ] ( [ / \ ], [ /\/\/\ ] ) ]
>>> from sage.all import * >>> A = B = DyckWords(Integer(3)) >>> bij = Bijectionist(A, B) >>> bij.set_statistics((lambda D: D.number_of_touch_points(), lambda D: D.number_of_initial_rises())) >>> ascii_art(sorted(bij.minimal_subdistributions_iterator())) [ ( [ /\ ] ) [ ( [ / \ ] ) ( [ /\ /\ ] [ /\ /\/\ ] ) [ ( [ /\/\/\ ], [ / \ ] ), ( [ /\/ \, / \/\ ], [ / \/\, / \ ] ), <BLANKLINE> ( [ /\ ] ) ] ( [ /\/\ / \ ] [ /\ ] ) ] ( [ / \, / \ ], [ /\/\/\, /\/ \ ] ) ] >>> bij.set_quadratic_relation((lambda D: D, lambda D: D)) >>> ascii_art(sorted(bij.minimal_subdistributions_iterator())) [ ( [ /\ ] ) [ ( [ / \ ] ) ( [ /\ ] [ /\/\ ] ) [ ( [ /\/\/\ ], [ / \ ] ), ( [ /\/ \ ], [ / \ ] ), <BLANKLINE> <BLANKLINE> ( [ /\ ] [ /\ ] ) ( [ /\/\ ] [ /\ ] ) ( [ / \/\ ], [ / \/\ ] ), ( [ / \ ], [ /\/ \ ] ), <BLANKLINE> ( [ /\ ] ) ] ( [ / \ ] ) ] ( [ / \ ], [ /\/\/\ ] ) ]
- set_semi_conjugacy(*pi_rho)[source]#
Add restrictions of the form \(s(\pi(a_1,\dots, a_k)) = \rho(s(a_1),\dots, s(a_k))\).
Warning
Any restriction imposed by a previous invocation of
set_intertwining_relations()will be overwritten!INPUT:
pi_rho– one or more tuples \((k, \pi: A^k\to A, \rho: Z^k\to Z, \tilde A)\) where \(\tilde A\) (optional) is a \(k\)-ary function that returns true if and only if a \(k\)-tuple of objects in \(A\) is in the domain of \(\pi\)
ALGORITHM:
The relation
\[s(\pi(a_1,\dots, a_k)) = \rho(s(a_1),\dots, s(a_k))\]for each pair \((\pi, \rho)\) implies immediately that \(s(\pi(a_1,\dots, a_k))\) only depends on the blocks of \(a_1,\dots, a_k\).
The MILP formulation is as follows. Let \(a_1,\dots,a_k \in A\) and let \(a = \pi(a_1,\dots,a_k)\). Let \(z_1,\dots,z_k \in Z\) and let \(z = \rho(z_1,\dots,z_k)\). Suppose that \(a_i\in p_i\) for all \(i\) and that \(a\in p\).
We then want to model the implication
\[x_{p_1, z_1} = 1,\dots, x_{p_k, z_k} = 1 \Rightarrow x_{p, z} = 1.\]We achieve this by requiring
\[x_{p, z}\geq 1 - k + \sum_{i=1}^k x_{p_i, z_i}.\]Note that \(z\) must be a possible value of \(p\) and each \(z_i\) must be a possible value of \(p_i\).
EXAMPLES:
We can concatenate two permutations by increasing the values of the second permutation by the length of the first permutation:
sage: def concat(p1, p2): return Permutation(p1 + [i + len(p1) for i in p2])
>>> from sage.all import * >>> def concat(p1, p2): return Permutation(p1 + [i + len(p1) for i in p2])
We may be interested in statistics on permutations which are equidistributed with the number of fixed points, such that concatenating permutations corresponds to adding statistic values:
sage: A = B = [permutation for n in range(4) for permutation in Permutations(n)] sage: bij = Bijectionist(A, B, Permutation.number_of_fixed_points) sage: bij.set_statistics((len, len)) sage: for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ....: print(solution) ... {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3} ... {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 1, [2, 1, 3]: 3, [2, 3, 1]: 0, [3, 1, 2]: 0, [3, 2, 1]: 1} ... sage: bij.set_intertwining_relations((2, concat, lambda x, y: x + y)) sage: for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ....: print(solution) {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 0}
>>> from sage.all import * >>> A = B = [permutation for n in range(Integer(4)) for permutation in Permutations(n)] >>> bij = Bijectionist(A, B, Permutation.number_of_fixed_points) >>> bij.set_statistics((len, len)) >>> for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ... print(solution) ... {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3} ... {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 1, [2, 1, 3]: 3, [2, 3, 1]: 0, [3, 1, 2]: 0, [3, 2, 1]: 1} ... >>> bij.set_intertwining_relations((Integer(2), concat, lambda x, y: x + y)) >>> for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ... print(solution) {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 0}
The domain of the composition may be restricted. E.g., if we concatenate only permutations starting with a 1, we obtain fewer forced elements:
sage: in_domain = lambda p1, p2: (not p1 or p1(1) == 1) and (not p2 or p2(1) == 1) sage: bij.set_intertwining_relations((2, concat, lambda x, y: x + y, in_domain)) sage: for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ....: print(solution) {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 0}
>>> from sage.all import * >>> in_domain = lambda p1, p2: (not p1 or p1(Integer(1)) == Integer(1)) and (not p2 or p2(Integer(1)) == Integer(1)) >>> bij.set_intertwining_relations((Integer(2), concat, lambda x, y: x + y, in_domain)) >>> for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ... print(solution) {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 0, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 1, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 2, [2, 1]: 0, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 0, [3, 2, 1]: 0}
We can also restrict according to several composition functions. For example, we may additionally concatenate permutations by incrementing the elements of the first:
sage: skew_concat = lambda p1, p2: Permutation([i + len(p2) for i in p1] + list(p2)) sage: bij.set_intertwining_relations((2, skew_concat, lambda x, y: x + y)) sage: for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ....: print(solution) {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 0, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 0, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3}
>>> from sage.all import * >>> skew_concat = lambda p1, p2: Permutation([i + len(p2) for i in p1] + list(p2)) >>> bij.set_intertwining_relations((Integer(2), skew_concat, lambda x, y: x + y)) >>> for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ... print(solution) {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 0, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 0, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 1, [3, 2, 1]: 3}
However, this yields no solution:
sage: bij.set_intertwining_relations((2, concat, lambda x, y: x + y), (2, skew_concat, lambda x, y: x + y)) sage: list(bij.solutions_iterator()) []
>>> from sage.all import * >>> bij.set_intertwining_relations((Integer(2), concat, lambda x, y: x + y), (Integer(2), skew_concat, lambda x, y: x + y)) >>> list(bij.solutions_iterator()) []
- set_statistics(*alpha_beta)[source]#
Set constraints of the form \(\alpha = \beta\circ S\).
Warning
Any restriction imposed by a previous invocation of
set_statistics()will be overwritten!INPUT:
alpha_beta– one or more pairs \((\alpha: A\to W, \beta: B\to W)\)
If the statistics \(\alpha\) and \(\beta\) are not equidistributed, an error is raised.
ALGORITHM:
We add
\[\sum_{a\in A, z\in Z} x_{p(a), z} s^z t^{\alpha(a)} = \sum_{b\in B} s^{\tau(b)} t(\beta(b))\]as a matrix equation to the MILP.
EXAMPLES:
We look for bijections \(S\) on permutations such that the number of weak exceedences of \(S(\pi)\) equals the number of descents of \(\pi\), and statistics \(s\), such that the number of fixed points of \(S(\pi)\) equals \(s(\pi)\):
sage: N = 4; A = B = [permutation for n in range(N) for permutation in Permutations(n)] sage: def wex(p): return len(p.weak_excedences()) sage: def fix(p): return len(p.fixed_points()) sage: def des(p): return len(p.descents(final_descent=True)) if p else 0 sage: def adj(p): return len([e for (e, f) in zip(p, p[1:]+[0]) if e == f+1]) sage: bij = Bijectionist(A, B, fix) sage: bij.set_statistics((wex, des), (len, len)) sage: for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ....: print(solution) {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 3, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 3, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 3, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 0, [3, 1, 2]: 3, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 3, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 3, [3, 2, 1]: 0} sage: bij = Bijectionist(A, B, fix) sage: bij.set_statistics((wex, des), (fix, adj), (len, len)) sage: for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ....: print(solution) {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 3, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 0, [3, 1, 2]: 3, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 3, [3, 2, 1]: 0}
>>> from sage.all import * >>> N = Integer(4); A = B = [permutation for n in range(N) for permutation in Permutations(n)] >>> def wex(p): return len(p.weak_excedences()) >>> def fix(p): return len(p.fixed_points()) >>> def des(p): return len(p.descents(final_descent=True)) if p else Integer(0) >>> def adj(p): return len([e for (e, f) in zip(p, p[Integer(1):]+[Integer(0)]) if e == f+Integer(1)]) >>> bij = Bijectionist(A, B, fix) >>> bij.set_statistics((wex, des), (len, len)) >>> for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ... print(solution) {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 3, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 3, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 1, [3, 1, 2]: 3, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 0, [3, 1, 2]: 3, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 1, [3, 1, 2]: 3, [3, 2, 1]: 0} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 3, [3, 2, 1]: 0} >>> bij = Bijectionist(A, B, fix) >>> bij.set_statistics((wex, des), (fix, adj), (len, len)) >>> for solution in sorted(list(bij.solutions_iterator()), key=lambda d: tuple(sorted(d.items()))): ... print(solution) {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 0, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 3, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 1, [2, 1, 3]: 0, [2, 3, 1]: 0, [3, 1, 2]: 3, [3, 2, 1]: 1} {[]: 0, [1]: 1, [1, 2]: 0, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 1, [2, 1, 3]: 1, [2, 3, 1]: 0, [3, 1, 2]: 3, [3, 2, 1]: 0}
Calling this with non-equidistributed statistics yields an error:
sage: bij = Bijectionist(A, B, fix) sage: bij.set_statistics((wex, fix)) Traceback (most recent call last): ... ValueError: statistics alpha and beta are not equidistributed
>>> from sage.all import * >>> bij = Bijectionist(A, B, fix) >>> bij.set_statistics((wex, fix)) Traceback (most recent call last): ... ValueError: statistics alpha and beta are not equidistributed
- set_value_restrictions(*value_restrictions)[source]#
Restrict the set of possible values \(s(a)\) for a given element \(a\).
Warning
Any restriction imposed by a previous invocation of
set_value_restrictions()will be overwritten!INPUT:
value_restrictions– one or more pairs \((a\in A, \tilde Z\subseteq Z)\)
EXAMPLES:
We may want to restrict the value of a given element to a single or multiple values. We do not require that the specified values are in the image of \(\tau\). In some cases, the restriction may not be able to provide a better solution, as for size 3 in the following example.
sage: A = B = [permutation for n in range(4) for permutation in Permutations(n)] sage: tau = Permutation.longest_increasing_subsequence_length sage: bij = Bijectionist(A, B, tau) sage: bij.set_statistics((len, len)) sage: bij.set_value_restrictions((Permutation([1, 2]), [1]), ....: (Permutation([3, 2, 1]), [2, 3, 4])) sage: for sol in sorted(bij.solutions_iterator(), key=lambda d: sorted(d.items())): ....: print(sol) {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 3, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 3, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 2, [2, 1, 3]: 3, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 3, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 3, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 3, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 1, [2, 1, 3]: 3, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 1, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 1, [2, 3, 1]: 2, [3, 1, 2]: 3, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 1, [2, 3, 1]: 3, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 1, [3, 1, 2]: 2, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 1, [3, 1, 2]: 3, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 1, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 3, [3, 1, 2]: 1, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 3, [2, 3, 1]: 1, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 3, [2, 3, 1]: 2, [3, 1, 2]: 1, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 3, [2, 1, 3]: 1, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 3, [2, 1, 3]: 2, [2, 3, 1]: 1, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 3, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 1, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 3, [1, 3, 2]: 2, [2, 1, 3]: 1, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 3, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 1, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 3, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 1, [3, 2, 1]: 2}
>>> from sage.all import * >>> A = B = [permutation for n in range(Integer(4)) for permutation in Permutations(n)] >>> tau = Permutation.longest_increasing_subsequence_length >>> bij = Bijectionist(A, B, tau) >>> bij.set_statistics((len, len)) >>> bij.set_value_restrictions((Permutation([Integer(1), Integer(2)]), [Integer(1)]), ... (Permutation([Integer(3), Integer(2), Integer(1)]), [Integer(2), Integer(3), Integer(4)])) >>> for sol in sorted(bij.solutions_iterator(), key=lambda d: sorted(d.items())): ... print(sol) {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 3, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 3, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 2, [2, 1, 3]: 3, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 1, [1, 3, 2]: 3, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 3, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 3, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 1, [2, 1, 3]: 3, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 1, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 1, [2, 3, 1]: 2, [3, 1, 2]: 3, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 1, [2, 3, 1]: 3, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 1, [3, 1, 2]: 2, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 1, [3, 1, 2]: 3, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 1, [3, 2, 1]: 3} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 3, [3, 1, 2]: 1, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 3, [2, 3, 1]: 1, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 2, [2, 1, 3]: 3, [2, 3, 1]: 2, [3, 1, 2]: 1, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 3, [2, 1, 3]: 1, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 3, [2, 1, 3]: 2, [2, 3, 1]: 1, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 2, [1, 3, 2]: 3, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 1, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 3, [1, 3, 2]: 1, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 3, [1, 3, 2]: 2, [2, 1, 3]: 1, [2, 3, 1]: 2, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 3, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 1, [3, 1, 2]: 2, [3, 2, 1]: 2} {[]: 0, [1]: 1, [1, 2]: 1, [2, 1]: 2, [1, 2, 3]: 3, [1, 3, 2]: 2, [2, 1, 3]: 2, [2, 3, 1]: 2, [3, 1, 2]: 1, [3, 2, 1]: 2}
However, an error occurs if the set of possible values is empty. In this example, the image of \(\tau\) under any legal bijection is disjoint to the specified values.
- solutions_iterator()[source]#
An iterator over all solutions of the problem.
OUTPUT: An iterator over all possible mappings \(s: A\to Z\)
ALGORITHM:
We solve an integer linear program with a binary variable \(x_{p, z}\) for each partition block \(p\in P\) and each statistic value \(z\in Z\):
\(x_{p, z} = 1\) if and only if \(s(a) = z\) for all \(a\in p\).
Then we add the constraint \(\sum_{x\in V} x<|V|\), where \(V\) is the set containing all \(x\) with \(x = 1\), that is, those indicator variables representing the current solution. Therefore, a solution of this new program must be different from all those previously obtained.
INTEGER LINEAR PROGRAM:
Let \(m_w(p)\), for a block \(p\) of \(P\), be the multiplicity of the value \(w\) in \(W\) under \(\alpha\), that is, the number of elements \(a \in p\) with \(\alpha(a)=w\).
Let \(n_w(z)\) be the number of elements \(b \in B\) with \(\beta(b)=w\) and \(\tau(b)=z\) for \(w \in W\), \(z \in Z\).
Let \(k\) be the arity of a pair \((\pi, \rho)\) in an intertwining relation.
and the following constraints:
because every block is assigned precisely one value, for all \(p\in P\),
\[\sum_z x_{p, z} = 1.\]because the statistics \(s\) and \(\tau\) and also \(\alpha\) and \(\beta\) are equidistributed, for all \(w\in W\) and \(z\in Z\),
\[\sum_p m_w(p) x_{p, z} = n_w(z).\]for each intertwining relation \(s(\pi(a_1,\dots, a_k)) = \rho(s(a_1),\dots, s(a_r))\), and for all \(k\)-combinations of blocks \(p_i\in P\) such that there exist \((a_1,\dots, a_k)\in p_1\times\dots\times p_k\) with \(\pi(a_1,\dots, a_k)\in W\) and \(z = \rho(z_1,\dots, z_k)\),
\[x_{p, z} \geq 1-k + \sum_{i=1}^k x_{p_i, z_i}.\]for each distribution restriction, i.e. a set of elements \(\tilde A\) and a distribution of values given by integers \(d_z\) representing the multiplicity of each \(z \in Z\), and \(r_p = |p \cap\tilde A|\) indicating the relative size of block \(p\) in the set of elements of the distribution,
\[\sum_p r_p x_{p, z} = d_z.\]EXAMPLES:
sage: A = B = 'abc' sage: bij = Bijectionist(A, B, lambda x: B.index(x) % 2, solver="GLPK") sage: next(bij.solutions_iterator()) {'a': 0, 'b': 1, 'c': 0} sage: list(bij.solutions_iterator()) [{'a': 0, 'b': 1, 'c': 0}, {'a': 1, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}] sage: N = 4 sage: A = B = [permutation for n in range(N) for permutation in Permutations(n)]
>>> from sage.all import * >>> A = B = 'abc' >>> bij = Bijectionist(A, B, lambda x: B.index(x) % Integer(2), solver="GLPK") >>> next(bij.solutions_iterator()) {'a': 0, 'b': 1, 'c': 0} >>> list(bij.solutions_iterator()) [{'a': 0, 'b': 1, 'c': 0}, {'a': 1, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}] >>> N = Integer(4) >>> A = B = [permutation for n in range(N) for permutation in Permutations(n)]
Let \(\tau\) be the number of non-left-to-right-maxima of a permutation:
sage: def tau(pi): ....: pi = list(pi) ....: i = count = 0 ....: for j in range(len(pi)): ....: if pi[j] > i: ....: i = pi[j] ....: else: ....: count += 1 ....: return count
>>> from sage.all import * >>> def tau(pi): ... pi = list(pi) ... i = count = Integer(0) ... for j in range(len(pi)): ... if pi[j] > i: ... i = pi[j] ... else: ... count += Integer(1) ... return count
We look for a statistic which is constant on conjugacy classes:
sage: P = [list(a) for n in range(N) for a in Permutations(n).conjugacy_classes()] sage: bij = Bijectionist(A, B, tau, solver="GLPK") sage: bij.set_statistics((len, len)) sage: bij.set_constant_blocks(P) sage: for solution in bij.solutions_iterator(): ....: print(solution) {[]: 0, [1]: 0, [1, 2]: 1, [2, 1]: 0, [1, 2, 3]: 0, [1, 3, 2]: 1, [2, 1, 3]: 1, [3, 2, 1]: 1, [2, 3, 1]: 2, [3, 1, 2]: 2} {[]: 0, [1]: 0, [1, 2]: 0, [2, 1]: 1, [1, 2, 3]: 0, [1, 3, 2]: 1, [2, 1, 3]: 1, [3, 2, 1]: 1, [2, 3, 1]: 2, [3, 1, 2]: 2}
>>> from sage.all import * >>> P = [list(a) for n in range(N) for a in Permutations(n).conjugacy_classes()] >>> bij = Bijectionist(A, B, tau, solver="GLPK") >>> bij.set_statistics((len, len)) >>> bij.set_constant_blocks(P) >>> for solution in bij.solutions_iterator(): ... print(solution) {[]: 0, [1]: 0, [1, 2]: 1, [2, 1]: 0, [1, 2, 3]: 0, [1, 3, 2]: 1, [2, 1, 3]: 1, [3, 2, 1]: 1, [2, 3, 1]: 2, [3, 1, 2]: 2} {[]: 0, [1]: 0, [1, 2]: 0, [2, 1]: 1, [1, 2, 3]: 0, [1, 3, 2]: 1, [2, 1, 3]: 1, [3, 2, 1]: 1, [2, 3, 1]: 2, [3, 1, 2]: 2}
Changing or re-setting problem parameters clears the internal cache. Setting the verbosity prints the MILP which is solved.:
sage: set_verbose(2) sage: bij.set_constant_blocks(P) sage: _ = list(bij.solutions_iterator()) Constraints are: block []: 1 <= x_0 <= 1 block [1]: 1 <= x_1 <= 1 block [1, 2]: 1 <= x_2 + x_3 <= 1 block [2, 1]: 1 <= x_4 + x_5 <= 1 block [1, 2, 3]: 1 <= x_6 + x_7 + x_8 <= 1 block [1, 3, 2]: 1 <= x_9 + x_10 + x_11 <= 1 block [2, 3, 1]: 1 <= x_12 + x_13 + x_14 <= 1 statistics: 1 <= x_0 <= 1 statistics: 0 <= <= 0 statistics: 0 <= <= 0 statistics: 1 <= x_1 <= 1 statistics: 0 <= <= 0 statistics: 0 <= <= 0 statistics: 1 <= x_2 + x_4 <= 1 statistics: 1 <= x_3 + x_5 <= 1 statistics: 0 <= <= 0 statistics: 1 <= x_6 + 3 x_9 + 2 x_12 <= 1 statistics: 3 <= x_7 + 3 x_10 + 2 x_13 <= 3 statistics: 2 <= x_8 + 3 x_11 + 2 x_14 <= 2 Variables are: x_0: s([]) = 0 x_1: s([1]) = 0 x_2: s([1, 2]) = 0 x_3: s([1, 2]) = 1 x_4: s([2, 1]) = 0 x_5: s([2, 1]) = 1 x_6: s([1, 2, 3]) = 0 x_7: s([1, 2, 3]) = 1 x_8: s([1, 2, 3]) = 2 x_9: s([1, 3, 2]) = s([2, 1, 3]) = s([3, 2, 1]) = 0 x_10: s([1, 3, 2]) = s([2, 1, 3]) = s([3, 2, 1]) = 1 x_11: s([1, 3, 2]) = s([2, 1, 3]) = s([3, 2, 1]) = 2 x_12: s([2, 3, 1]) = s([3, 1, 2]) = 0 x_13: s([2, 3, 1]) = s([3, 1, 2]) = 1 x_14: s([2, 3, 1]) = s([3, 1, 2]) = 2 after vetoing Constraints are: block []: 1 <= x_0 <= 1 block [1]: 1 <= x_1 <= 1 block [1, 2]: 1 <= x_2 + x_3 <= 1 block [2, 1]: 1 <= x_4 + x_5 <= 1 block [1, 2, 3]: 1 <= x_6 + x_7 + x_8 <= 1 block [1, 3, 2]: 1 <= x_9 + x_10 + x_11 <= 1 block [2, 3, 1]: 1 <= x_12 + x_13 + x_14 <= 1 statistics: 1 <= x_0 <= 1 statistics: 0 <= <= 0 statistics: 0 <= <= 0 statistics: 1 <= x_1 <= 1 statistics: 0 <= <= 0 statistics: 0 <= <= 0 statistics: 1 <= x_2 + x_4 <= 1 statistics: 1 <= x_3 + x_5 <= 1 statistics: 0 <= <= 0 statistics: 1 <= x_6 + 3 x_9 + 2 x_12 <= 1 statistics: 3 <= x_7 + 3 x_10 + 2 x_13 <= 3 statistics: 2 <= x_8 + 3 x_11 + 2 x_14 <= 2 veto: x_0 + x_1 + x_3 + x_4 + x_6 + x_10 + x_14 <= 6 after vetoing Constraints are: block []: 1 <= x_0 <= 1 block [1]: 1 <= x_1 <= 1 block [1, 2]: 1 <= x_2 + x_3 <= 1 block [2, 1]: 1 <= x_4 + x_5 <= 1 block [1, 2, 3]: 1 <= x_6 + x_7 + x_8 <= 1 block [1, 3, 2]: 1 <= x_9 + x_10 + x_11 <= 1 block [2, 3, 1]: 1 <= x_12 + x_13 + x_14 <= 1 statistics: 1 <= x_0 <= 1 statistics: 0 <= <= 0 statistics: 0 <= <= 0 statistics: 1 <= x_1 <= 1 statistics: 0 <= <= 0 statistics: 0 <= <= 0 statistics: 1 <= x_2 + x_4 <= 1 statistics: 1 <= x_3 + x_5 <= 1 statistics: 0 <= <= 0 statistics: 1 <= x_6 + 3 x_9 + 2 x_12 <= 1 statistics: 3 <= x_7 + 3 x_10 + 2 x_13 <= 3 statistics: 2 <= x_8 + 3 x_11 + 2 x_14 <= 2 veto: x_0 + x_1 + x_3 + x_4 + x_6 + x_10 + x_14 <= 6 veto: x_0 + x_1 + x_2 + x_5 + x_6 + x_10 + x_14 <= 6 sage: set_verbose(0)
>>> from sage.all import * >>> set_verbose(Integer(2)) >>> bij.set_constant_blocks(P) >>> _ = list(bij.solutions_iterator()) Constraints are: block []: 1 <= x_0 <= 1 block [1]: 1 <= x_1 <= 1 block [1, 2]: 1 <= x_2 + x_3 <= 1 block [2, 1]: 1 <= x_4 + x_5 <= 1 block [1, 2, 3]: 1 <= x_6 + x_7 + x_8 <= 1 block [1, 3, 2]: 1 <= x_9 + x_10 + x_11 <= 1 block [2, 3, 1]: 1 <= x_12 + x_13 + x_14 <= 1 statistics: 1 <= x_0 <= 1 statistics: 0 <= <= 0 statistics: 0 <= <= 0 statistics: 1 <= x_1 <= 1 statistics: 0 <= <= 0 statistics: 0 <= <= 0 statistics: 1 <= x_2 + x_4 <= 1 statistics: 1 <= x_3 + x_5 <= 1 statistics: 0 <= <= 0 statistics: 1 <= x_6 + 3 x_9 + 2 x_12 <= 1 statistics: 3 <= x_7 + 3 x_10 + 2 x_13 <= 3 statistics: 2 <= x_8 + 3 x_11 + 2 x_14 <= 2 Variables are: x_0: s([]) = 0 x_1: s([1]) = 0 x_2: s([1, 2]) = 0 x_3: s([1, 2]) = 1 x_4: s([2, 1]) = 0 x_5: s([2, 1]) = 1 x_6: s([1, 2, 3]) = 0 x_7: s([1, 2, 3]) = 1 x_8: s([1, 2, 3]) = 2 x_9: s([1, 3, 2]) = s([2, 1, 3]) = s([3, 2, 1]) = 0 x_10: s([1, 3, 2]) = s([2, 1, 3]) = s([3, 2, 1]) = 1 x_11: s([1, 3, 2]) = s([2, 1, 3]) = s([3, 2, 1]) = 2 x_12: s([2, 3, 1]) = s([3, 1, 2]) = 0 x_13: s([2, 3, 1]) = s([3, 1, 2]) = 1 x_14: s([2, 3, 1]) = s([3, 1, 2]) = 2 after vetoing Constraints are: block []: 1 <= x_0 <= 1 block [1]: 1 <= x_1 <= 1 block [1, 2]: 1 <= x_2 + x_3 <= 1 block [2, 1]: 1 <= x_4 + x_5 <= 1 block [1, 2, 3]: 1 <= x_6 + x_7 + x_8 <= 1 block [1, 3, 2]: 1 <= x_9 + x_10 + x_11 <= 1 block [2, 3, 1]: 1 <= x_12 + x_13 + x_14 <= 1 statistics: 1 <= x_0 <= 1 statistics: 0 <= <= 0 statistics: 0 <= <= 0 statistics: 1 <= x_1 <= 1 statistics: 0 <= <= 0 statistics: 0 <= <= 0 statistics: 1 <= x_2 + x_4 <= 1 statistics: 1 <= x_3 + x_5 <= 1 statistics: 0 <= <= 0 statistics: 1 <= x_6 + 3 x_9 + 2 x_12 <= 1 statistics: 3 <= x_7 + 3 x_10 + 2 x_13 <= 3 statistics: 2 <= x_8 + 3 x_11 + 2 x_14 <= 2 veto: x_0 + x_1 + x_3 + x_4 + x_6 + x_10 + x_14 <= 6 after vetoing Constraints are: block []: 1 <= x_0 <= 1 block [1]: 1 <= x_1 <= 1 block [1, 2]: 1 <= x_2 + x_3 <= 1 block [2, 1]: 1 <= x_4 + x_5 <= 1 block [1, 2, 3]: 1 <= x_6 + x_7 + x_8 <= 1 block [1, 3, 2]: 1 <= x_9 + x_10 + x_11 <= 1 block [2, 3, 1]: 1 <= x_12 + x_13 + x_14 <= 1 statistics: 1 <= x_0 <= 1 statistics: 0 <= <= 0 statistics: 0 <= <= 0 statistics: 1 <= x_1 <= 1 statistics: 0 <= <= 0 statistics: 0 <= <= 0 statistics: 1 <= x_2 + x_4 <= 1 statistics: 1 <= x_3 + x_5 <= 1 statistics: 0 <= <= 0 statistics: 1 <= x_6 + 3 x_9 + 2 x_12 <= 1 statistics: 3 <= x_7 + 3 x_10 + 2 x_13 <= 3 statistics: 2 <= x_8 + 3 x_11 + 2 x_14 <= 2 veto: x_0 + x_1 + x_3 + x_4 + x_6 + x_10 + x_14 <= 6 veto: x_0 + x_1 + x_2 + x_5 + x_6 + x_10 + x_14 <= 6 >>> set_verbose(Integer(0))
- statistics_fibers()[source]#
Return a dictionary mapping statistic values in \(W\) to their preimages in \(A\) and \(B\).
This is a (computationally) fast way to obtain a first impression which objects in \(A\) should be mapped to which objects in \(B\).
EXAMPLES:
sage: A = B = [permutation for n in range(4) for permutation in Permutations(n)] sage: tau = Permutation.longest_increasing_subsequence_length sage: def wex(p): return len(p.weak_excedences()) sage: def fix(p): return len(p.fixed_points()) sage: def des(p): return len(p.descents(final_descent=True)) if p else 0 sage: def adj(p): return len([e for (e, f) in zip(p, p[1:]+[0]) if e == f+1]) sage: bij = Bijectionist(A, B, tau) sage: bij.set_statistics((len, len), (wex, des), (fix, adj)) sage: table([[key, AB[0], AB[1]] for key, AB in bij.statistics_fibers().items()]) (0, 0, 0) [[]] [[]] (1, 1, 1) [[1]] [[1]] (2, 2, 2) [[1, 2]] [[2, 1]] (2, 1, 0) [[2, 1]] [[1, 2]] (3, 3, 3) [[1, 2, 3]] [[3, 2, 1]] (3, 2, 1) [[1, 3, 2], [2, 1, 3], [3, 2, 1]] [[1, 3, 2], [2, 1, 3], [2, 3, 1]] (3, 2, 0) [[2, 3, 1]] [[3, 1, 2]] (3, 1, 0) [[3, 1, 2]] [[1, 2, 3]]
>>> from sage.all import * >>> A = B = [permutation for n in range(Integer(4)) for permutation in Permutations(n)] >>> tau = Permutation.longest_increasing_subsequence_length >>> def wex(p): return len(p.weak_excedences()) >>> def fix(p): return len(p.fixed_points()) >>> def des(p): return len(p.descents(final_descent=True)) if p else Integer(0) >>> def adj(p): return len([e for (e, f) in zip(p, p[Integer(1):]+[Integer(0)]) if e == f+Integer(1)]) >>> bij = Bijectionist(A, B, tau) >>> bij.set_statistics((len, len), (wex, des), (fix, adj)) >>> table([[key, AB[Integer(0)], AB[Integer(1)]] for key, AB in bij.statistics_fibers().items()]) (0, 0, 0) [[]] [[]] (1, 1, 1) [[1]] [[1]] (2, 2, 2) [[1, 2]] [[2, 1]] (2, 1, 0) [[2, 1]] [[1, 2]] (3, 3, 3) [[1, 2, 3]] [[3, 2, 1]] (3, 2, 1) [[1, 3, 2], [2, 1, 3], [3, 2, 1]] [[1, 3, 2], [2, 1, 3], [2, 3, 1]] (3, 2, 0) [[2, 3, 1]] [[3, 1, 2]] (3, 1, 0) [[3, 1, 2]] [[1, 2, 3]]
- statistics_table(header=True)[source]#
Provide information about all elements of \(A\) with corresponding \(\alpha\) values and all elements of \(B\) with corresponding \(\beta\) and \(\tau\) values.
INPUT:
header– (default:True) whether to include a header with the standard Greek letters
OUTPUT:
A pair of lists suitable for
table, wherethe first contains the elements of \(A\) together with the values of \(\alpha\)
the second contains the elements of \(B\) together with the values of \(\tau\) and \(\beta\)
EXAMPLES:
sage: A = B = [permutation for n in range(4) for permutation in Permutations(n)] sage: tau = Permutation.longest_increasing_subsequence_length sage: def wex(p): return len(p.weak_excedences()) sage: def fix(p): return len(p.fixed_points()) sage: def des(p): return len(p.descents(final_descent=True)) if p else 0 sage: def adj(p): return len([e for (e, f) in zip(p, p[1:]+[0]) if e == f+1]) sage: bij = Bijectionist(A, B, tau) sage: bij.set_statistics((wex, des), (fix, adj)) sage: a, b = bij.statistics_table() sage: table(a, header_row=True, frame=True) ┌───────────┬────────┬────────┐ │ a | α_1(a) | α_2(a) | ╞═══════════╪════════╪════════╡ │ [] | 0 | 0 | ├───────────┼────────┼────────┤ │ [1] | 1 | 1 | ├───────────┼────────┼────────┤ │ [1, 2] | 2 | 2 | ├───────────┼────────┼────────┤ │ [2, 1] | 1 | 0 | ├───────────┼────────┼────────┤ │ [1, 2, 3] | 3 | 3 | ├───────────┼────────┼────────┤ │ [1, 3, 2] | 2 | 1 | ├───────────┼────────┼────────┤ │ [2, 1, 3] | 2 | 1 | ├───────────┼────────┼────────┤ │ [2, 3, 1] | 2 | 0 | ├───────────┼────────┼────────┤ │ [3, 1, 2] | 1 | 0 | ├───────────┼────────┼────────┤ │ [3, 2, 1] | 2 | 1 | └───────────┴────────┴────────┘ sage: table(b, header_row=True, frame=True) ┌───────────┬───┬────────┬────────┐ │ b | τ | β_1(b) | β_2(b) | ╞═══════════╪═══╪════════╪════════╡ │ [] | 0 | 0 | 0 | ├───────────┼───┼────────┼────────┤ │ [1] | 1 | 1 | 1 | ├───────────┼───┼────────┼────────┤ │ [1, 2] | 2 | 1 | 0 | ├───────────┼───┼────────┼────────┤ │ [2, 1] | 1 | 2 | 2 | ├───────────┼───┼────────┼────────┤ │ [1, 2, 3] | 3 | 1 | 0 | ├───────────┼───┼────────┼────────┤ │ [1, 3, 2] | 2 | 2 | 1 | ├───────────┼───┼────────┼────────┤ │ [2, 1, 3] | 2 | 2 | 1 | ├───────────┼───┼────────┼────────┤ │ [2, 3, 1] | 2 | 2 | 1 | ├───────────┼───┼────────┼────────┤ │ [3, 1, 2] | 2 | 2 | 0 | ├───────────┼───┼────────┼────────┤ │ [3, 2, 1] | 1 | 3 | 3 | └───────────┴───┴────────┴────────┘
>>> from sage.all import * >>> A = B = [permutation for n in range(Integer(4)) for permutation in Permutations(n)] >>> tau = Permutation.longest_increasing_subsequence_length >>> def wex(p): return len(p.weak_excedences()) >>> def fix(p): return len(p.fixed_points()) >>> def des(p): return len(p.descents(final_descent=True)) if p else Integer(0) >>> def adj(p): return len([e for (e, f) in zip(p, p[Integer(1):]+[Integer(0)]) if e == f+Integer(1)]) >>> bij = Bijectionist(A, B, tau) >>> bij.set_statistics((wex, des), (fix, adj)) >>> a, b = bij.statistics_table() >>> table(a, header_row=True, frame=True) ┌───────────┬────────┬────────┐ │ a | α_1(a) | α_2(a) | ╞═══════════╪════════╪════════╡ │ [] | 0 | 0 | ├───────────┼────────┼────────┤ │ [1] | 1 | 1 | ├───────────┼────────┼────────┤ │ [1, 2] | 2 | 2 | ├───────────┼────────┼────────┤ │ [2, 1] | 1 | 0 | ├───────────┼────────┼────────┤ │ [1, 2, 3] | 3 | 3 | ├───────────┼────────┼────────┤ │ [1, 3, 2] | 2 | 1 | ├───────────┼────────┼────────┤ │ [2, 1, 3] | 2 | 1 | ├───────────┼────────┼────────┤ │ [2, 3, 1] | 2 | 0 | ├───────────┼────────┼────────┤ │ [3, 1, 2] | 1 | 0 | ├───────────┼────────┼────────┤ │ [3, 2, 1] | 2 | 1 | └───────────┴────────┴────────┘ >>> table(b, header_row=True, frame=True) ┌───────────┬───┬────────┬────────┐ │ b | τ | β_1(b) | β_2(b) | ╞═══════════╪═══╪════════╪════════╡ │ [] | 0 | 0 | 0 | ├───────────┼───┼────────┼────────┤ │ [1] | 1 | 1 | 1 | ├───────────┼───┼────────┼────────┤ │ [1, 2] | 2 | 1 | 0 | ├───────────┼───┼────────┼────────┤ │ [2, 1] | 1 | 2 | 2 | ├───────────┼───┼────────┼────────┤ │ [1, 2, 3] | 3 | 1 | 0 | ├───────────┼───┼────────┼────────┤ │ [1, 3, 2] | 2 | 2 | 1 | ├───────────┼───┼────────┼────────┤ │ [2, 1, 3] | 2 | 2 | 1 | ├───────────┼───┼────────┼────────┤ │ [2, 3, 1] | 2 | 2 | 1 | ├───────────┼───┼────────┼────────┤ │ [3, 1, 2] | 2 | 2 | 0 | ├───────────┼───┼────────┼────────┤ │ [3, 2, 1] | 1 | 3 | 3 | └───────────┴───┴────────┴────────┘