A bijectionist’s toolkit

AUTHORS:

• Alexander Grosz, Tobias Kietreiber, Stephan Pfannerer and Martin Rubey (2020-2022): Initial version

Quick reference

set_statistics()	Declare statistics that are preserved by the bijection.
set_value_restrictions()	Restrict the values of the statistic on an element.
set_constant_blocks()	Declare that the statistic is constant on some sets.
set_distributions()	Restrict the distribution of values of the statistic on some elements.
set_intertwining_relations()	Declare that the statistic intertwines with other maps.
set_quadratic_relation()	Declare that the statistic satisfies a certain relation.
set_homomesic()	Declare that the statistic is homomesic with respect to a given set partition.
statistics_table()	Print a table collecting information on the given statistics.
statistics_fibers()	Collect elements with the same statistics.
constant_blocks()	Return the blocks on which the statistic is constant.
solutions_iterator()	Iterate over all possible solutions.
possible_values()	Return all possible values for a given element.
minimal_subdistributions_iterator()	Iterate over the minimal subdistributions.
minimal_subdistributions_blocks_iterator()	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

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}

Python

>>> 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

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])

Python

>>> 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

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())
[]

Python

>>> 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

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     ] )

Python

>>> 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

sage: findmap(list(bij.minimal_subdistributions_iterator()))            # optional -- internet
0: Mp00034 (quality [100])
1: Mp00061oMp00023 (quality [100])
2: Mp00018oMp00140 (quality [100])

Python

>>> 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)

Bases: SageObject

A toolbox to list all possible bijections between two finite sets under various constraints.

INPUT:

• A, B – sets of equal size, given as a list

• tau – (optional) a function from B to Z, in case of None, the identity map lambda x: x is used

• alpha_beta – (optional) a list of pairs of statistics alpha from A to W and beta from B to W

• P – (optional) a partition of A

• pi_rho – (optional) a list of triples (k, pi, rho), where

  • pi – a k-ary operation composing objects in A and

  • rho – a k-ary function composing statistic values in Z

• elements_distributions – (optional) a list of pairs (tA, tZ), specifying the distributions of tA

• value_restrictions – (optional) a list of pairs (a, tZ), restricting the possible values of a

• solver – (optional) the backend used to solve the mixed integer linear programs

W and Z can 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{array}{r}\begin{array}{rr}& A\\ \alpha \swarrow & S\downarrow & \searrow s\\ W\stackrel{\beta }{\leftarrow }& B& \stackrel{\tau }{\to }Z\end{array}\begin{array}{lcl}{A}^k& \stackrel{\pi }{\to }& A\\ \downarrow s^k& & \downarrow s\\ Z^k& \stackrel{\rho }{\to }& Z\end{array}\end{array}$$

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)

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 – boolean (default: False); whether or not to include singleton blocks in the output

• optimal – boolean (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

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'}}

Python

>>> 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()

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

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])]

Python

>>> 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

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])

Python

>>> 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

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])]

Python

>>> 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

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])]

Python

>>> 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

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])]

Python

>>> 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

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)}

Python

>>> 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

sage: sorted(D) in [d for d, _ in bij.minimal_subdistributions_iterator()]
True

Python

>>> from sage.all import *
>>> sorted(D) in [d for d, _ in bij.minimal_subdistributions_iterator()]
True

minimal_subdistributions_iterator()

Return all minimal subsets $\tilde{A}$ of $A$ together with submultisets $\tilde{Z}$ with $s(\tilde{A})=\tilde{Z}$ as multisets.

EXAMPLES:

Sage

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])]

Python

>>> 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

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])

Python

>>> 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

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])]

Python

>>> 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)

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 these

• optimal – boolean (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=True does not update the internal dictionary, because this would interfere with the variables of the MILP.

EXAMPLES:

Sage

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}}

Python

>>> 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

sage: bij.possible_values(A)
{'a': {1, 2}, 'b': {1, 2}, 'c': {1, 2}, 'd': {1, 2}}

Python

>>> from sage.all import *
>>> bij.possible_values(A)
{'a': {1, 2}, 'b': {1, 2}, 'c': {1, 2}, 'd': {1, 2}}

set_constant_blocks(P)

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 by set_intertwining_relations() and solutions_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 – 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

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'}}

Python

>>> 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

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'}}

Python

>>> 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

sage: bij.set_constant_blocks([['a', 'b']])
sage: bij.constant_blocks()
{{'a', 'b'}}

Python

>>> 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

sage: bij.constant_blocks(optimal=True)
Traceback (most recent call last):
...
StopIteration

Python

>>> from sage.all import *
>>> bij.constant_blocks(optimal=True)
Traceback (most recent call last):
...
StopIteration

set_distributions(*elements_distributions)

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

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])]

Python

>>> 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

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])]

Python

>>> 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)

Assert that the average of $s$ on each block of $Q$ is constant.

INPUT:

• Q – set partition of A

EXAMPLES:

Sage

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}]

Python

>>> 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)

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}\ge 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

sage: def concat(p1, p2): return Permutation(p1 + [i + len(p1) for i in p2])

Python

>>> 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

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}

Python

>>> 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

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}

Python

>>> 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

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}

Python

>>> 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

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())
[]

Python

>>> 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)

Add restrictions of the form $s\circ \psi \circ s=\varphi$.

INPUT:

• phi_psi – (optional) a list of pairs $(\varphi ,\rho )$ where $\varphi :A\to Z$ and $\psi :Z\to A$

ALGORITHM:

We add

$$x_{p(a),z}=x_{p(\psi (z)),\varphi (a)}$$

for $a\in A$ and $z\in Z$ to the MILP, where $\varphi :A\to Z$ and $\psi :Z\to A$. Note that, in particular, $\varphi$ must be constant on blocks.

EXAMPLES:

Sage

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()))
[ (             [   /\   ] )
[ (             [  /  \  ] )  ( [    /\  ]  [  /\/\  ] )
[ ( [ /\/\/\ ], [ /    \ ] ), ( [ /\/  \ ], [ /    \ ] ),


 ( [  /\    ]  [  /\    ] )  ( [  /\/\  ]  [    /\  ] )
 ( [ /  \/\ ], [ /  \/\ ] ), ( [ /    \ ], [ /\/  \ ] ),

 ( [   /\   ]             ) ]
 ( [  /  \  ]             ) ]
 ( [ /    \ ], [ /\/\/\ ] ) ]

Python

>>> 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)

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}\ge 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

sage: def concat(p1, p2): return Permutation(p1 + [i + len(p1) for i in p2])

Python

>>> 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

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}

Python

>>> 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

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}

Python

>>> 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

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}

Python

>>> 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

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())
[]

Python

>>> 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)

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

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}

Python

>>> 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

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

Python

>>> 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)

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

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}

Python

>>> 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()

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 \cdots \times p_k$ with $\pi (a_1,\dots ,a_k)\in W$ and $z=\rho (z_1,\dots ,z_k)$,

$$x_{p,z}\ge 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

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)]

Python

>>> 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

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

Python

>>> 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

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}

Python

>>> 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

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)

Python

>>> 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()

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

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]]

Python

>>> 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)

Provide information about all elements of $A$ with corresponding $\alpha$ values and all elements of $B$ with corresponding $\beta$ and $\tau$ values.

INPUT:

• header – boolean (default: True); whether to include a header with the standard Greek letters

OUTPUT:

A pair of lists suitable for table, where

• the 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

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      |
└───────────┴───┴────────┴────────┘

Python

>>> 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      |
└───────────┴───┴────────┴────────┘