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

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

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

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

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

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

  • optimal – (optional, 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'}}
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: 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])]

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

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

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

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

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

But it is, by design, included here:

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

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

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])]
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 – (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: 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}}

The internal dictionary is not updated:

sage: 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 – 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'}}

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

Setting constant blocks overrides any previous assignment:

sage: bij.set_constant_blocks([['a', 'b']])
sage: 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
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: 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])]

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])]
set_homomesic(Q)#

Assert that the average of \(s\) on each block of \(Q\) is constant.

INPUT:

  • Q – a set partition of A

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

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}

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}

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}

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())
[]
set_quadratic_relation(*phi_psi)#

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


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

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

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}

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}

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}

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

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

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

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

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}

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)
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: 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]]
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 – (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: 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      |
└───────────┴───┴────────┴────────┘