(Non-negative) Integer vectors¶

AUTHORS:

Mike Hansen (2007) - original module
Nathann Cohen, David Joyner (2009-2010) - Gale-Ryser stuff
Nathann Cohen, David Joyner (2011) - Gale-Ryser bugfix
Travis Scrimshaw (2012-05-12) - Updated doc-strings to tell the user of that the class’s name is a misnomer (that they only contains non-negative entries).
Federico Poloni (2013) - specialized rank()
Travis Scrimshaw (2013-02-04) - Refactored to use ClonableIntArray

class sage.combinat.integer_vector.IntegerVector[source]¶

Bases: ClonableArray

An integer vector.

check()[source]¶

Check to make sure this is a valid integer vector by making sure all entries are nonnegative.

EXAMPLES:

Sage

sage: IV = IntegerVectors()
sage: elt = IV([1,2,1])
sage: elt.check()

Python

>>> from sage.all import *
>>> IV = IntegerVectors()
>>> elt = IV([Integer(1),Integer(2),Integer(1)])
>>> elt.check()

Check Issue #34510:

Sage

sage: IV3 = IntegerVectors(n=3)
sage: IV3([2,2])
Traceback (most recent call last):
...
ValueError: [2, 2] doesn't satisfy correct constraints
sage: IVk3 = IntegerVectors(k=3)
sage: IVk3([2,2])
Traceback (most recent call last):
...
ValueError: [2, 2] doesn't satisfy correct constraints
sage: IV33 = IntegerVectors(n=3, k=3)
sage: IV33([2,2])
Traceback (most recent call last):
...
ValueError: [2, 2] doesn't satisfy correct constraints

Python

>>> from sage.all import *
>>> IV3 = IntegerVectors(n=Integer(3))
>>> IV3([Integer(2),Integer(2)])
Traceback (most recent call last):
...
ValueError: [2, 2] doesn't satisfy correct constraints
>>> IVk3 = IntegerVectors(k=Integer(3))
>>> IVk3([Integer(2),Integer(2)])
Traceback (most recent call last):
...
ValueError: [2, 2] doesn't satisfy correct constraints
>>> IV33 = IntegerVectors(n=Integer(3), k=Integer(3))
>>> IV33([Integer(2),Integer(2)])
Traceback (most recent call last):
...
ValueError: [2, 2] doesn't satisfy correct constraints

specht_module(base_ring=None)[source]¶

Return the Specht module corresponding to self.

EXAMPLES:

Sage

sage: SM = IntegerVectors()([2,0,1,0,2]).specht_module(QQ); SM              # needs sage.combinat sage.modules
Specht module of [(0, 0), (0, 1), (2, 0), (4, 0), (4, 1)] over Rational Field
sage: s = SymmetricFunctions(QQ).s()                                        # needs sage.combinat sage.modules
sage: s(SM.frobenius_image())                                               # needs sage.combinat sage.modules
s[2, 2, 1]

Python

>>> from sage.all import *
>>> SM = IntegerVectors()([Integer(2),Integer(0),Integer(1),Integer(0),Integer(2)]).specht_module(QQ); SM              # needs sage.combinat sage.modules
Specht module of [(0, 0), (0, 1), (2, 0), (4, 0), (4, 1)] over Rational Field
>>> s = SymmetricFunctions(QQ).s()                                        # needs sage.combinat sage.modules
>>> s(SM.frobenius_image())                                               # needs sage.combinat sage.modules
s[2, 2, 1]

specht_module_dimension(base_ring=None)[source]¶

Return the dimension of the Specht module corresponding to self.

INPUT:

BR – (default: \(\QQ\)) the base ring

EXAMPLES:

Sage

sage: IntegerVectors()([2,0,1,0,2]).specht_module_dimension()               # needs sage.combinat sage.modules
5
sage: IntegerVectors()([2,0,1,0,2]).specht_module_dimension(GF(2))          # needs sage.combinat sage.modules sage.rings.finite_rings
5

Python

>>> from sage.all import *
>>> IntegerVectors()([Integer(2),Integer(0),Integer(1),Integer(0),Integer(2)]).specht_module_dimension()               # needs sage.combinat sage.modules
5
>>> IntegerVectors()([Integer(2),Integer(0),Integer(1),Integer(0),Integer(2)]).specht_module_dimension(GF(Integer(2)))          # needs sage.combinat sage.modules sage.rings.finite_rings
5

trim()[source]¶

Remove trailing zeros from the integer vector.

EXAMPLES:

Sage

sage: IV = IntegerVectors()
sage: IV([5,3,5,1,0,0]).trim()
[5, 3, 5, 1]
sage: IV([5,0,5,1,0]).trim()
[5, 0, 5, 1]
sage: IV([4,3,3]).trim()
[4, 3, 3]
sage: IV([0,0,0]).trim()
[]

sage: IV = IntegerVectors(k=4)
sage: v = IV([4,3,2,0]).trim(); v
[4, 3, 2]
sage: v.parent()
Integer vectors

Python

>>> from sage.all import *
>>> IV = IntegerVectors()
>>> IV([Integer(5),Integer(3),Integer(5),Integer(1),Integer(0),Integer(0)]).trim()
[5, 3, 5, 1]
>>> IV([Integer(5),Integer(0),Integer(5),Integer(1),Integer(0)]).trim()
[5, 0, 5, 1]
>>> IV([Integer(4),Integer(3),Integer(3)]).trim()
[4, 3, 3]
>>> IV([Integer(0),Integer(0),Integer(0)]).trim()
[]

>>> IV = IntegerVectors(k=Integer(4))
>>> v = IV([Integer(4),Integer(3),Integer(2),Integer(0)]).trim(); v
[4, 3, 2]
>>> v.parent()
Integer vectors

class sage.combinat.integer_vector.IntegerVectors(category=None)[source]¶

Bases: Parent

The class of (nonnegative) integer vectors.

INPUT:

n – if set to an integer, returns the combinatorial class of integer vectors whose sum is n; if set to None (default), no such constraint is defined
k – the length of the vectors; set to None (default) if you do not want such a constraint

Note

The entries are nonnegative integers.

EXAMPLES:

If n is not specified, it returns the class of all integer vectors:

Sage

sage: IntegerVectors()
Integer vectors
sage: [] in IntegerVectors()
True
sage: [1,2,1] in IntegerVectors()
True
sage: [1, 0, 0] in IntegerVectors()
True

Python

>>> from sage.all import *
>>> IntegerVectors()
Integer vectors
>>> [] in IntegerVectors()
True
>>> [Integer(1),Integer(2),Integer(1)] in IntegerVectors()
True
>>> [Integer(1), Integer(0), Integer(0)] in IntegerVectors()
True

Entries are nonnegative:

Sage

sage: [-1, 2] in IntegerVectors()
False

Python

>>> from sage.all import *
>>> [-Integer(1), Integer(2)] in IntegerVectors()
False

If n is specified, then it returns the class of all integer vectors which sum to n:

Sage

sage: IV3 = IntegerVectors(3); IV3
Integer vectors that sum to 3

Python

>>> from sage.all import *
>>> IV3 = IntegerVectors(Integer(3)); IV3
Integer vectors that sum to 3

Note that trailing zeros are ignored so that [3, 0] does not show up in the following list (since [3] does):

Sage

sage: IntegerVectors(3, max_length=2).list()
[[3], [2, 1], [1, 2], [0, 3]]

Python

>>> from sage.all import *
>>> IntegerVectors(Integer(3), max_length=Integer(2)).list()
[[3], [2, 1], [1, 2], [0, 3]]

If n and k are both specified, then it returns the class of integer vectors that sum to n and are of length k:

Sage

sage: IV53 = IntegerVectors(5,3); IV53
Integer vectors of length 3 that sum to 5
sage: IV53.cardinality()
21
sage: IV53.first()
[5, 0, 0]
sage: IV53.last()
[0, 0, 5]
sage: IV53.random_element().parent() is IV53
True

Python

>>> from sage.all import *
>>> IV53 = IntegerVectors(Integer(5),Integer(3)); IV53
Integer vectors of length 3 that sum to 5
>>> IV53.cardinality()
21
>>> IV53.first()
[5, 0, 0]
>>> IV53.last()
[0, 0, 5]
>>> IV53.random_element().parent() is IV53
True

Further examples:

Sage

sage: IntegerVectors(-1, 0, min_part=1).list()
[]
sage: IntegerVectors(-1, 2, min_part=1).list()
[]
sage: IntegerVectors(0, 0, min_part=1).list()
[[]]
sage: IntegerVectors(3, 0, min_part=1).list()
[]
sage: IntegerVectors(0, 1, min_part=1).list()
[]
sage: IntegerVectors(2, 2, min_part=1).list()
[[1, 1]]
sage: IntegerVectors(2, 3, min_part=1).list()
[]
sage: IntegerVectors(4, 2, min_part=1).list()
[[3, 1], [2, 2], [1, 3]]

Python

>>> from sage.all import *
>>> IntegerVectors(-Integer(1), Integer(0), min_part=Integer(1)).list()
[]
>>> IntegerVectors(-Integer(1), Integer(2), min_part=Integer(1)).list()
[]
>>> IntegerVectors(Integer(0), Integer(0), min_part=Integer(1)).list()
[[]]
>>> IntegerVectors(Integer(3), Integer(0), min_part=Integer(1)).list()
[]
>>> IntegerVectors(Integer(0), Integer(1), min_part=Integer(1)).list()
[]
>>> IntegerVectors(Integer(2), Integer(2), min_part=Integer(1)).list()
[[1, 1]]
>>> IntegerVectors(Integer(2), Integer(3), min_part=Integer(1)).list()
[]
>>> IntegerVectors(Integer(4), Integer(2), min_part=Integer(1)).list()
[[3, 1], [2, 2], [1, 3]]

Sage

sage: IntegerVectors(0, 3, outer=[0,0,0]).list()
[[0, 0, 0]]
sage: IntegerVectors(1, 3, outer=[0,0,0]).list()
[]
sage: IntegerVectors(2, 3, outer=[0,2,0]).list()
[[0, 2, 0]]
sage: IntegerVectors(2, 3, outer=[1,2,1]).list()
[[1, 1, 0], [1, 0, 1], [0, 2, 0], [0, 1, 1]]
sage: IntegerVectors(2, 3, outer=[1,1,1]).list()
[[1, 1, 0], [1, 0, 1], [0, 1, 1]]
sage: IntegerVectors(2, 5, outer=[1,1,1,1,1]).list()
[[1, 1, 0, 0, 0],
 [1, 0, 1, 0, 0],
 [1, 0, 0, 1, 0],
 [1, 0, 0, 0, 1],
 [0, 1, 1, 0, 0],
 [0, 1, 0, 1, 0],
 [0, 1, 0, 0, 1],
 [0, 0, 1, 1, 0],
 [0, 0, 1, 0, 1],
 [0, 0, 0, 1, 1]]

Python

>>> from sage.all import *
>>> IntegerVectors(Integer(0), Integer(3), outer=[Integer(0),Integer(0),Integer(0)]).list()
[[0, 0, 0]]
>>> IntegerVectors(Integer(1), Integer(3), outer=[Integer(0),Integer(0),Integer(0)]).list()
[]
>>> IntegerVectors(Integer(2), Integer(3), outer=[Integer(0),Integer(2),Integer(0)]).list()
[[0, 2, 0]]
>>> IntegerVectors(Integer(2), Integer(3), outer=[Integer(1),Integer(2),Integer(1)]).list()
[[1, 1, 0], [1, 0, 1], [0, 2, 0], [0, 1, 1]]
>>> IntegerVectors(Integer(2), Integer(3), outer=[Integer(1),Integer(1),Integer(1)]).list()
[[1, 1, 0], [1, 0, 1], [0, 1, 1]]
>>> IntegerVectors(Integer(2), Integer(5), outer=[Integer(1),Integer(1),Integer(1),Integer(1),Integer(1)]).list()
[[1, 1, 0, 0, 0],
 [1, 0, 1, 0, 0],
 [1, 0, 0, 1, 0],
 [1, 0, 0, 0, 1],
 [0, 1, 1, 0, 0],
 [0, 1, 0, 1, 0],
 [0, 1, 0, 0, 1],
 [0, 0, 1, 1, 0],
 [0, 0, 1, 0, 1],
 [0, 0, 0, 1, 1]]

Sage

sage: iv = [ IntegerVectors(n,k) for n in range(-2, 7) for k in range(7) ]
sage: all(map(lambda x: x.cardinality() == len(x.list()), iv))
True
sage: essai = [[1,1,1], [2,5,6], [6,5,2]]
sage: iv = [ IntegerVectors(x[0], x[1], max_part = x[2]-1) for x in essai ]
sage: all(map(lambda x: x.cardinality() == len(x.list()), iv))
True

Python

>>> from sage.all import *
>>> iv = [ IntegerVectors(n,k) for n in range(-Integer(2), Integer(7)) for k in range(Integer(7)) ]
>>> all(map(lambda x: x.cardinality() == len(x.list()), iv))
True
>>> essai = [[Integer(1),Integer(1),Integer(1)], [Integer(2),Integer(5),Integer(6)], [Integer(6),Integer(5),Integer(2)]]
>>> iv = [ IntegerVectors(x[Integer(0)], x[Integer(1)], max_part = x[Integer(2)]-Integer(1)) for x in essai ]
>>> all(map(lambda x: x.cardinality() == len(x.list()), iv))
True

An example showing the same output by using IntegerListsLex:

Sage

sage: IntegerVectors(4, max_length=2).list()
[[4], [3, 1], [2, 2], [1, 3], [0, 4]]
sage: list(IntegerListsLex(4, max_length=2))
[[4], [3, 1], [2, 2], [1, 3], [0, 4]]

Python

>>> from sage.all import *
>>> IntegerVectors(Integer(4), max_length=Integer(2)).list()
[[4], [3, 1], [2, 2], [1, 3], [0, 4]]
>>> list(IntegerListsLex(Integer(4), max_length=Integer(2)))
[[4], [3, 1], [2, 2], [1, 3], [0, 4]]

Element[source]¶: alias of IntegerVector

class sage.combinat.integer_vector.IntegerVectorsConstraints(n=None, k=None, **constraints)[source]¶

Bases: IntegerVectors

Class of integer vectors subject to various constraints.

cardinality()[source]¶

Return the cardinality of self.

EXAMPLES:

Sage

sage: IntegerVectors(3, 3, min_part=1).cardinality()
1
sage: IntegerVectors(5, 3, min_part=1).cardinality()
6
sage: IntegerVectors(13, 4, max_part=4).cardinality()
20
sage: IntegerVectors(k=4, max_part=3).cardinality()
256
sage: IntegerVectors(k=3, min_part=2, max_part=4).cardinality()
27
sage: IntegerVectors(13, 4, min_part=2, max_part=4).cardinality()
16

Python

>>> from sage.all import *
>>> IntegerVectors(Integer(3), Integer(3), min_part=Integer(1)).cardinality()
1
>>> IntegerVectors(Integer(5), Integer(3), min_part=Integer(1)).cardinality()
6
>>> IntegerVectors(Integer(13), Integer(4), max_part=Integer(4)).cardinality()
20
>>> IntegerVectors(k=Integer(4), max_part=Integer(3)).cardinality()
256
>>> IntegerVectors(k=Integer(3), min_part=Integer(2), max_part=Integer(4)).cardinality()
27
>>> IntegerVectors(Integer(13), Integer(4), min_part=Integer(2), max_part=Integer(4)).cardinality()
16

class sage.combinat.integer_vector.IntegerVectors_all[source]¶

Bases: UniqueRepresentation, IntegerVectors

Class of all integer vectors.

class sage.combinat.integer_vector.IntegerVectors_k(k)[source]¶

Bases: UniqueRepresentation, IntegerVectors

Integer vectors of length \(k\).

cardinality()[source]¶

Return the cardinality of self.

EXAMPLES:

Sage

sage: IntegerVectors(k=0).cardinality()
1
sage: IntegerVectors(k=10).cardinality()
+Infinity

Python

>>> from sage.all import *
>>> IntegerVectors(k=Integer(0)).cardinality()
1
>>> IntegerVectors(k=Integer(10)).cardinality()
+Infinity

rank(x)[source]¶

Return the rank of a given element.

INPUT:

x – list with len(x) == k

EXAMPLES:

Sage

sage: IntegerVectors(k=5).rank([0,0,0,0,0])
0
sage: IntegerVectors(k=5).rank([1,1,0,0,0])
7

Python

>>> from sage.all import *
>>> IntegerVectors(k=Integer(5)).rank([Integer(0),Integer(0),Integer(0),Integer(0),Integer(0)])
0
>>> IntegerVectors(k=Integer(5)).rank([Integer(1),Integer(1),Integer(0),Integer(0),Integer(0)])
7

unrank(x)[source]¶

Return the element at given rank x.

INPUT:

x – integer such that x < self.cardinality()

EXAMPLES:

Sage

sage: IntegerVectors(k=5).unrank(10)
[1, 0, 0, 0, 1]
sage: IntegerVectors(k=5).unrank(15)
[0, 0, 2, 0, 0]
sage: IntegerVectors(k=0).unrank(0)
[]

Python

>>> from sage.all import *
>>> IntegerVectors(k=Integer(5)).unrank(Integer(10))
[1, 0, 0, 0, 1]
>>> IntegerVectors(k=Integer(5)).unrank(Integer(15))
[0, 0, 2, 0, 0]
>>> IntegerVectors(k=Integer(0)).unrank(Integer(0))
[]

class sage.combinat.integer_vector.IntegerVectors_n(n)[source]¶

Bases: UniqueRepresentation, IntegerVectors

Integer vectors that sum to \(n\).

cardinality()[source]¶

Return the cardinality of self.

EXAMPLES:

Sage

sage: IntegerVectors(n=0).cardinality()
1
sage: IntegerVectors(n=10).cardinality()
+Infinity

Python

>>> from sage.all import *
>>> IntegerVectors(n=Integer(0)).cardinality()
1
>>> IntegerVectors(n=Integer(10)).cardinality()
+Infinity

rank(x)[source]¶

Return the rank of a given element.

INPUT:

x – list with sum(x) == n

EXAMPLES:

Sage

sage: IntegerVectors(n=5).rank([5,0])
1
sage: IntegerVectors(n=5).rank([3,2])
3

Python

>>> from sage.all import *
>>> IntegerVectors(n=Integer(5)).rank([Integer(5),Integer(0)])
1
>>> IntegerVectors(n=Integer(5)).rank([Integer(3),Integer(2)])
3

unrank(x)[source]¶

Return the element at given rank x.

INPUT:

x – integer

EXAMPLES:

Sage

sage: IntegerVectors(n=5).unrank(2)
[4, 1]
sage: IntegerVectors(n=10).unrank(10)
[1, 9]

Python

>>> from sage.all import *
>>> IntegerVectors(n=Integer(5)).unrank(Integer(2))
[4, 1]
>>> IntegerVectors(n=Integer(10)).unrank(Integer(10))
[1, 9]

class sage.combinat.integer_vector.IntegerVectors_nk(n, k)[source]¶

Bases: UniqueRepresentation, IntegerVectors

Integer vectors of length \(k\) that sum to \(n\).

AUTHORS:

Martin Albrecht
Mike Hansen

cardinality()[source]¶

Return the cardinality of self.

EXAMPLES:

Sage

sage: IntegerVectors(3,5).cardinality()
35
sage: IntegerVectors(99, 3).cardinality()
5050
sage: IntegerVectors(10^9 - 1, 3).cardinality()
500000000500000000

Python

>>> from sage.all import *
>>> IntegerVectors(Integer(3),Integer(5)).cardinality()
35
>>> IntegerVectors(Integer(99), Integer(3)).cardinality()
5050
>>> IntegerVectors(Integer(10)**Integer(9) - Integer(1), Integer(3)).cardinality()
500000000500000000

rank(x)[source]¶

Return the rank of a given element.

INPUT:

x – list with sum(x) == n and len(x) == k

unrank(x)[source]¶

Return the element at given rank x.

INPUT:

x – integer such that x < self.cardinality()

EXAMPLES:

Sage

sage: IntegerVectors(4,5).unrank(30)
[1, 0, 1, 0, 2]
sage: IntegerVectors(2,3).unrank(5)
[0, 0, 2]

Python

>>> from sage.all import *
>>> IntegerVectors(Integer(4),Integer(5)).unrank(Integer(30))
[1, 0, 1, 0, 2]
>>> IntegerVectors(Integer(2),Integer(3)).unrank(Integer(5))
[0, 0, 2]

class sage.combinat.integer_vector.IntegerVectors_nnondescents(n, comp)[source]¶

Bases: UniqueRepresentation, IntegerVectors

Integer vectors graded by two parameters.

The grading parameters on the integer vector \(v\) are:

n – the sum of the parts of \(v\)
c – the non descents composition of \(v\)

In other words: the length of \(v\) equals \(c_1 + \cdots + c_k\), and \(v\) is decreasing in the consecutive blocs of length \(c_1, \ldots, c_k\),

INPUT:

n – the positive integer \(n\)
comp – the composition \(c\)

Those are the integer vectors of sum \(n\) that are lexicographically maximal (for the natural left-to-right reading) in their orbit by the Young subgroup \(S_{c_1} \times \cdots \times S_{c_k}\). In particular, they form a set of orbit representative of integer vectors with respect to this Young subgroup.

sage.combinat.integer_vector.gale_ryser_theorem(p1, p2, algorithm, solver, integrality_tolerance='gale')[source]¶

Return the binary matrix given by the Gale-Ryser theorem.

The Gale Ryser theorem asserts that if \(p_1,p_2\) are two partitions of \(n\) of respective lengths \(k_1,k_2\), then there is a binary \(k_1\times k_2\) matrix \(M\) such that \(p_1\) is the vector of row sums and \(p_2\) is the vector of column sums of \(M\), if and only if the conjugate of \(p_2\) dominates \(p_1\).

INPUT:

p1, p2 – list of integers representing the vectors of row/column sums
algorithm – two possible string values:
- 'ryser' implements the construction due to Ryser [Ryser63].
- 'gale' (default) implements the construction due to Gale [Gale57].
solver – (default: None) specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
integrality_tolerance – parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values()

OUTPUT: a binary matrix if it exists, None otherwise

Gale’s Algorithm:

(Gale [Gale57]): A matrix satisfying the constraints of its sums can be defined as the solution of the following Linear Program, which Sage knows how to solve.

\[\begin{split}\forall i&\sum_{j=1}^{k_2} b_{i,j}=p_{1,j}\\ \forall i&\sum_{j=1}^{k_1} b_{j,i}=p_{2,j}\\ &b_{i,j}\mbox{ is a binary variable}\end{split}\]

Ryser’s Algorithm:

(Ryser [Ryser63]): The construction of an \(m \times n\) matrix \(A=A_{r,s}\), due to Ryser, is described as follows. The construction works if and only if have \(s\preceq r^*\).

Construct the \(m \times n\) matrix \(B\) from \(r\) by defining the \(i\)-th row of \(B\) to be the vector whose first \(r_i\) entries are \(1\), and the remainder are 0s, \(1 \leq i \leq m\). This maximal matrix \(B\) with row sum \(r\) and ones left justified has column sum \(r^{*}\).
Shift the last \(1\) in certain rows of \(B\) to column \(n\) in order to achieve the sum \(s_n\). Call this \(B\) again.
- The \(1\)’s in column \(n\) are to appear in those rows in which \(A\) has the largest row sums, giving preference to the bottom-most positions in case of ties.
- Note: When this step automatically “fixes” other columns, one must skip ahead to the first column index with a wrong sum in the step below.
Proceed inductively to construct columns \(n-1\), …, \(2\), \(1\). Note: when performing the induction on step \(k\), we consider the row sums of the first \(k\) columns.
Set \(A = B\). Return \(A\).

EXAMPLES:

Computing the matrix for \(p_1=p_2=2+2+1\):

Sage

sage: # needs sage.combinat sage.modules
sage: from sage.combinat.integer_vector import gale_ryser_theorem
sage: p1 = [2,2,1]
sage: p2 = [2,2,1]
sage: print(gale_ryser_theorem(p1, p2))         # not tested
[1 1 0]
[1 0 1]
[0 1 0]
sage: A = gale_ryser_theorem(p1, p2)
sage: rs = [sum(x) for x in A.rows()]
sage: cs = [sum(x) for x in A.columns()]
sage: p1 == rs; p2 == cs
True
True

Python

>>> from sage.all import *
>>> # needs sage.combinat sage.modules
>>> from sage.combinat.integer_vector import gale_ryser_theorem
>>> p1 = [Integer(2),Integer(2),Integer(1)]
>>> p2 = [Integer(2),Integer(2),Integer(1)]
>>> print(gale_ryser_theorem(p1, p2))         # not tested
[1 1 0]
[1 0 1]
[0 1 0]
>>> A = gale_ryser_theorem(p1, p2)
>>> rs = [sum(x) for x in A.rows()]
>>> cs = [sum(x) for x in A.columns()]
>>> p1 == rs; p2 == cs
True
True

Or for a non-square matrix with \(p_1=3+3+2+1\) and \(p_2=3+2+2+1+1\), using Ryser’s algorithm:

Sage

sage: # needs sage.combinat sage.modules
sage: from sage.combinat.integer_vector import gale_ryser_theorem
sage: p1 = [3,3,1,1]
sage: p2 = [3,3,1,1]
sage: gale_ryser_theorem(p1, p2, algorithm='ryser')
[1 1 1 0]
[1 1 0 1]
[1 0 0 0]
[0 1 0 0]
sage: p1 = [4,2,2]
sage: p2 = [3,3,1,1]
sage: gale_ryser_theorem(p1, p2, algorithm='ryser')
[1 1 1 1]
[1 1 0 0]
[1 1 0 0]
sage: p1 = [4,2,2,0]
sage: p2 = [3,3,1,1,0,0]
sage: gale_ryser_theorem(p1, p2, algorithm='ryser')
[1 1 1 1 0 0]
[1 1 0 0 0 0]
[1 1 0 0 0 0]
[0 0 0 0 0 0]
sage: p1 = [3,3,2,1]
sage: p2 = [3,2,2,1,1]
sage: print(gale_ryser_theorem(p1, p2, algorithm='gale'))       # not tested
[1 1 1 0 0]
[1 1 0 0 1]
[1 0 1 0 0]
[0 0 0 1 0]

Python

>>> from sage.all import *
>>> # needs sage.combinat sage.modules
>>> from sage.combinat.integer_vector import gale_ryser_theorem
>>> p1 = [Integer(3),Integer(3),Integer(1),Integer(1)]
>>> p2 = [Integer(3),Integer(3),Integer(1),Integer(1)]
>>> gale_ryser_theorem(p1, p2, algorithm='ryser')
[1 1 1 0]
[1 1 0 1]
[1 0 0 0]
[0 1 0 0]
>>> p1 = [Integer(4),Integer(2),Integer(2)]
>>> p2 = [Integer(3),Integer(3),Integer(1),Integer(1)]
>>> gale_ryser_theorem(p1, p2, algorithm='ryser')
[1 1 1 1]
[1 1 0 0]
[1 1 0 0]
>>> p1 = [Integer(4),Integer(2),Integer(2),Integer(0)]
>>> p2 = [Integer(3),Integer(3),Integer(1),Integer(1),Integer(0),Integer(0)]
>>> gale_ryser_theorem(p1, p2, algorithm='ryser')
[1 1 1 1 0 0]
[1 1 0 0 0 0]
[1 1 0 0 0 0]
[0 0 0 0 0 0]
>>> p1 = [Integer(3),Integer(3),Integer(2),Integer(1)]
>>> p2 = [Integer(3),Integer(2),Integer(2),Integer(1),Integer(1)]
>>> print(gale_ryser_theorem(p1, p2, algorithm='gale'))       # not tested
[1 1 1 0 0]
[1 1 0 0 1]
[1 0 1 0 0]
[0 0 0 1 0]

With \(0\) in the sequences, and with unordered inputs:

Sage

sage: from sage.combinat.integer_vector import gale_ryser_theorem
sage: gale_ryser_theorem([3,3,0,1,1,0], [3,1,3,1,0], algorithm='ryser')         # needs sage.combinat sage.modules
[1 1 1 0 0]
[1 0 1 1 0]
[0 0 0 0 0]
[1 0 0 0 0]
[0 0 1 0 0]
[0 0 0 0 0]
sage: p1 = [3,1,1,1,1]; p2 = [3,2,2,0]
sage: gale_ryser_theorem(p1, p2, algorithm='ryser')                             # needs sage.combinat sage.modules
[1 1 1 0]
[1 0 0 0]
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]

Python

>>> from sage.all import *
>>> from sage.combinat.integer_vector import gale_ryser_theorem
>>> gale_ryser_theorem([Integer(3),Integer(3),Integer(0),Integer(1),Integer(1),Integer(0)], [Integer(3),Integer(1),Integer(3),Integer(1),Integer(0)], algorithm='ryser')         # needs sage.combinat sage.modules
[1 1 1 0 0]
[1 0 1 1 0]
[0 0 0 0 0]
[1 0 0 0 0]
[0 0 1 0 0]
[0 0 0 0 0]
>>> p1 = [Integer(3),Integer(1),Integer(1),Integer(1),Integer(1)]; p2 = [Integer(3),Integer(2),Integer(2),Integer(0)]
>>> gale_ryser_theorem(p1, p2, algorithm='ryser')                             # needs sage.combinat sage.modules
[1 1 1 0]
[1 0 0 0]
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]

REFERENCES:

[Ryser63] (1,2)

H. J. Ryser, Combinatorial Mathematics, Carus Monographs, MAA, 1963.

[Gale57] (1,2)

D. Gale, A theorem on flows in networks, Pacific J. Math. 7(1957)1073-1082.

sage.combinat.integer_vector.integer_vectors_nk_fast_iter(n, k)[source]¶

A fast iterator for integer vectors of n of length k which yields Python lists filled with Sage Integers.

EXAMPLES:

Sage

sage: from sage.combinat.integer_vector import integer_vectors_nk_fast_iter
sage: list(integer_vectors_nk_fast_iter(3, 2))
[[3, 0], [2, 1], [1, 2], [0, 3]]
sage: list(integer_vectors_nk_fast_iter(2, 2))
[[2, 0], [1, 1], [0, 2]]
sage: list(integer_vectors_nk_fast_iter(1, 2))
[[1, 0], [0, 1]]

Python

>>> from sage.all import *
>>> from sage.combinat.integer_vector import integer_vectors_nk_fast_iter
>>> list(integer_vectors_nk_fast_iter(Integer(3), Integer(2)))
[[3, 0], [2, 1], [1, 2], [0, 3]]
>>> list(integer_vectors_nk_fast_iter(Integer(2), Integer(2)))
[[2, 0], [1, 1], [0, 2]]
>>> list(integer_vectors_nk_fast_iter(Integer(1), Integer(2)))
[[1, 0], [0, 1]]

We check some corner cases:

Sage

sage: list(integer_vectors_nk_fast_iter(5, 1))
[[5]]
sage: list(integer_vectors_nk_fast_iter(1, 1))
[[1]]
sage: list(integer_vectors_nk_fast_iter(2, 0))
[]
sage: list(integer_vectors_nk_fast_iter(0, 2))
[[0, 0]]
sage: list(integer_vectors_nk_fast_iter(0, 0))
[[]]

Python

>>> from sage.all import *
>>> list(integer_vectors_nk_fast_iter(Integer(5), Integer(1)))
[[5]]
>>> list(integer_vectors_nk_fast_iter(Integer(1), Integer(1)))
[[1]]
>>> list(integer_vectors_nk_fast_iter(Integer(2), Integer(0)))
[]
>>> list(integer_vectors_nk_fast_iter(Integer(0), Integer(2)))
[[0, 0]]
>>> list(integer_vectors_nk_fast_iter(Integer(0), Integer(0)))
[[]]

sage.combinat.integer_vector.is_gale_ryser(r, s)[source]¶

Test whether the given sequences satisfy the condition of the Gale-Ryser theorem.

Given a binary matrix \(B\) of dimension \(n\times m\), the vector of row sums is defined as the vector whose \(i^{\mbox{th}}\) component is equal to the sum of the \(i^{\mbox{th}}\) row in \(A\). The vector of column sums is defined similarly.

If, given a binary matrix, these two vectors are easy to compute, the Gale-Ryser theorem lets us decide whether, given two nonnegative vectors \(r,s\), there exists a binary matrix whose row/column sums vectors are \(r\) and \(s\).

This functions answers accordingly.

INPUT:

r, s – lists of nonnegative integers

ALGORITHM:

Without loss of generality, we can assume that:

The two given sequences do not contain any \(0\) ( which would correspond to an empty column/row )
The two given sequences are ordered in decreasing order (reordering the sequence of row (resp. column) sums amounts to reordering the rows (resp. columns) themselves in the matrix, which does not alter the columns (resp. rows) sums.

We can then assume that \(r\) and \(s\) are partitions (see the corresponding class Partition)

If \(r^*\) denote the conjugate of \(r\), the Gale-Ryser theorem asserts that a binary Matrix satisfying the constraints exists if and only if \(s \preceq r^*\), where \(\preceq\) denotes the domination order on partitions.

EXAMPLES:

Sage

sage: from sage.combinat.integer_vector import is_gale_ryser
sage: is_gale_ryser([4,2,2], [3,3,1,1])                                         # needs sage.combinat
True
sage: is_gale_ryser([4,2,1,1], [3,3,1,1])                                       # needs sage.combinat
True
sage: is_gale_ryser([3,2,1,1], [3,3,1,1])                                       # needs sage.combinat
False

Python

>>> from sage.all import *
>>> from sage.combinat.integer_vector import is_gale_ryser
>>> is_gale_ryser([Integer(4),Integer(2),Integer(2)], [Integer(3),Integer(3),Integer(1),Integer(1)])                                         # needs sage.combinat
True
>>> is_gale_ryser([Integer(4),Integer(2),Integer(1),Integer(1)], [Integer(3),Integer(3),Integer(1),Integer(1)])                                       # needs sage.combinat
True
>>> is_gale_ryser([Integer(3),Integer(2),Integer(1),Integer(1)], [Integer(3),Integer(3),Integer(1),Integer(1)])                                       # needs sage.combinat
False

REMARK: In the literature, what we are calling a Gale-Ryser sequence sometimes goes by the (rather generic-sounding) term ‘’realizable sequence’’.

sage.combinat.integer_vector.list2func(l, default=None)[source]¶

Given a list l, return a function that takes in a value i and return l[i]. If default is not None, then the function will return the default value for out of range i’s.

EXAMPLES:

Sage

sage: f = sage.combinat.integer_vector.list2func([1,2,3])
sage: f(0)
1
sage: f(1)
2
sage: f(2)
3
sage: f(3)
Traceback (most recent call last):
...
IndexError: list index out of range

Python

>>> from sage.all import *
>>> f = sage.combinat.integer_vector.list2func([Integer(1),Integer(2),Integer(3)])
>>> f(Integer(0))
1
>>> f(Integer(1))
2
>>> f(Integer(2))
3
>>> f(Integer(3))
Traceback (most recent call last):
...
IndexError: list index out of range

Sage

sage: f = sage.combinat.integer_vector.list2func([1,2,3], 0)
sage: f(2)
3
sage: f(3)
0

Python

>>> from sage.all import *
>>> f = sage.combinat.integer_vector.list2func([Integer(1),Integer(2),Integer(3)], Integer(0))
>>> f(Integer(2))
3
>>> f(Integer(3))
0