Integer vectors¶

AUTHORS:

Mike Hanson (2007) - original module

Nathann Cohen, David Joyner (2009-2010) - Gale-Ryser stuff

sage.combinat.integer_vector.IntegerVectors(n=None, k=None, **kwargs)¶

Returns the combinatorial class of integer vectors.

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

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

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

sage: IV3 = IntegerVectors(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: IntegerVectors(3, max_length=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: 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()
[4, 0, 1]

class sage.combinat.integer_vector.IntegerVectors_all(category=None, *keys, **opts)¶

Bases: sage.combinat.combinat.CombinatorialClass

cardinality()¶

EXAMPLES:

sage: IntegerVectors().cardinality()
+Infinity

list()¶

EXAMPLES:

sage: IntegerVectors().list()
...
NotImplementedError: infinite list

class sage.combinat.integer_vector.IntegerVectors_nconstraints(n, constraints)¶

Bases: sage.combinat.integer_vector.IntegerVectors_nkconstraints

cardinality()¶

EXAMPLES:

sage: IntegerVectors(3, max_length=2).cardinality()
4
sage: IntegerVectors(3).cardinality()
+Infinity

list()¶

EXAMPLES:

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

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

Bases: sage.combinat.combinat.CombinatorialClass

list()¶

EXAMPLE:

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

class sage.combinat.integer_vector.IntegerVectors_nkconstraints(n, k, constraints)¶

Bases: sage.combinat.combinat.CombinatorialClass

cardinality()¶

EXAMPLES:

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

first()¶

EXAMPLES:

sage: IntegerVectors(2,3,min_slope=0).first()
[0, 1, 1]

next(x)¶

EXAMPLES:

sage: IntegerVectors(2,3,min_slope=0).last()
[0, 0, 2]

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

Bases: sage.combinat.combinat.CombinatorialClass

The combinatorial class of integer vectors v graded by two parameters:

n: the sum of the parts of v
comp: the non descents composition of v

In other words: the length of v equals c[1]+...+c[k], and v is decreasing in the consecutive blocs of length c[1], ..., c[k]

Those are the integer vectors of sum n which are lexicographically maximal (for the natural left->right reading) in their orbit by the young subgroup S_c_1 x x S_c_k. In particular, they form a set of orbit representative of integer vectors w.r.t. this young subgroup.

sage.combinat.integer_vector.constant_func(i)¶

Returns the constant function i.

EXAMPLES:

sage: f = sage.combinat.integer_vector.constant_func(3)
sage: f(-1)
3
sage: f('asf')
3

sage.combinat.integer_vector.gale_ryser_theorem(p1, p2, algorithm='ryser')¶

Returns 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" (default) implements the construction due to Ryser [Ryser63].
- "gale" implements the construction due to Gale [Gale57].

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 (requires packages GLPK or CBC).

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

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 0’s, $1\leq i\leq m$ . This maximal matrix $B$ with row sum $r$ and ones left justified has column sum $r^{*}$ .
Shift the last in certain rows of to column in order to achieve the sum . Call this 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$ .
Set $A = B$ . Return $A$ .

EXAMPLES:

Computing the matrix for $p_1=p_2=2+2+1$

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, algorithm="gale") # Optional - requires GLPK or CBC
[0 1 1]
[1 1 0]
[1 0 0]       

Or for a non-square matrix with $p_1=3+3+2+1$ and $p_2=3+2+2+1+1$

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)
[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)
[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)
[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") # Optional - requires GLPK or CBC
[1 0 1 1 0]
[1 0 1 0 1]
[1 1 0 0 0]
[0 1 0 0 0]

With $0$ in the sequences, and with unordered inputs

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

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.is_gale_ryser(r, s)¶

Tests 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 non-negative vectors $r,s$ , there exists a binary matrix whose row/colum sums vectors are $r$ and $s$ .

This functions answers accordingly.

INPUT:

r, s – lists of non-negative 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: from sage.combinat.integer_vector import is_gale_ryser
sage: is_gale_ryser([4,2,2],[3,3,1,1])
True
sage: is_gale_ryser([4,2,1,1],[3,3,1,1])
True
sage: is_gale_ryser([3,2,1,1],[3,3,1,1])
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)¶

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

EXAMPLES:

sage: f = sage.combinat.integer_vector.list2func([1,2,3])
sage: f(1)
1
sage: f(2)
2
sage: f(3)
3
sage: f(4)
...
IndexError: list index out of range

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

Integer vectors¶

Previous topic

Next topic

This Page

Navigation

Integer vectors¶

Previous topic

Next topic

This Page

Quick search

Navigation