(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()
-
sage.combinat.integer_vector.
IntegerVectors
(n=None, k=None, **kwargs)¶ Returns the combinatorial class of (non-negative) integer vectors.
INPUT:
– if set to an integer, returns the combinatorial class of integer vectors whose sum is
. If set to
None
(default), no such constraint is defined.k
– the length of the vectors. Set toNone
(default) if you do not want such a constraint.
All other arguments given to this function are forwarded to the instance of
IntegerVectors_all
IntegerVectors_nconstraints
IntegerVectors_nk
orIntegerVectors_nkconstraints
that it returns.NOTE - These integer vectors are non-negative.
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
Entries are non-negative.
sage: [-1, 2] in IntegerVectors() False
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]
Further examples:
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]]
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]]
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
TESTS:
sage: IntegerVectors(None, length=3) Traceback (most recent call last): ... TypeError: __init__() got an unexpected keyword argument 'length' sage: IntegerVectors(None, 4) Traceback (most recent call last): ... NotImplementedError: k must be None when n is None
-
class
sage.combinat.integer_vector.
IntegerVectors_all
(category=None)¶ Bases:
sage.combinat.combinat.CombinatorialClass
TESTS:
sage: C = sage.combinat.combinat.CombinatorialClass() sage: C.category() Category of enumerated sets sage: C.__class__ <class 'sage.combinat.combinat.CombinatorialClass_with_category'> sage: isinstance(C, Parent) True sage: C = sage.combinat.combinat.CombinatorialClass(category = FiniteEnumeratedSets()) sage: C.category() Category of finite enumerated sets
-
cardinality
()¶ EXAMPLES:
sage: IntegerVectors().cardinality() +Infinity
-
list
()¶ EXAMPLES:
sage: IntegerVectors().list() Traceback (most recent call last): ... NotImplementedError: infinite list
-
-
class
sage.combinat.integer_vector.
IntegerVectors_nconstraints
(n, constraints)¶ Bases:
sage.combinat.integer_vector.IntegerVectors_nkconstraints
TESTS:
sage: IV = IntegerVectors(3, max_length=2) sage: IV == loads(dumps(IV)) True sage: IntegerVectors(3, max_length=2).cardinality() 4 sage: IntegerVectors(3).cardinality() +Infinity sage: IntegerVectors(3, max_length=2).list() [[3], [2, 1], [1, 2], [0, 3]] sage: IntegerVectors(3).list() Traceback (most recent call last): ... NotImplementedError: infinite list
-
class
sage.combinat.integer_vector.
IntegerVectors_nk
(n, k)¶ Bases:
sage.combinat.combinat.CombinatorialClass
TESTS:
sage: IV = IntegerVectors(2,3) sage: IV == loads(dumps(IV)) True
AUTHORS:
- Martin Albrecht
- Mike Hansen
-
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]]
-
rank
(x)¶ Returns the position of a given element.
INPUT:
x
- a list withsum(x) == n
andlen(x) == k
TESTS:
sage: IV = IntegerVectors(4,5) sage: range(IV.cardinality()) == [IV.rank(x) for x in IV] True
-
class
sage.combinat.integer_vector.
IntegerVectors_nkconstraints
(n, k, constraints, category=None)¶ Bases:
sage.combinat.integer_list.IntegerListsLex
EXAMPLES:
sage: IV = IntegerVectors(2,3,min_slope=0) sage: IV == loads(dumps(IV)) True sage: v = IntegerVectors(2,3,min_slope=0).first(); v [0, 1, 1] sage: type(v) <type 'list'>
TESTS:
All the attributes below are private; don’t use them!
sage: IV._min_length 3 sage: IV._max_length 3 sage: floor = IV._floor sage: [floor(i) for i in range(1,10)] [0, 0, 0, 0, 0, 0, 0, 0, 0] sage: ceiling = IV._ceiling sage: [ceiling(i) for i in range(1,5)] [inf, inf, inf, inf] sage: IV._min_slope 0 sage: IV._max_slope inf sage: IV = IntegerVectors(3, 10, inner=[4,1,3], min_part=2) sage: floor = IV._floor sage: floor(0), floor(1), floor(2) (4, 2, 3) sage: IV = IntegerVectors(3, 10, outer=[4,1,3], max_part=3) sage: ceiling = IV._ceiling sage: ceiling(0), ceiling(1), ceiling(2) (3, 1, 3)
-
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
-
next
(x)¶ EXAMPLES:
sage: a = IntegerVectors(2,3,min_slope=0).first() sage: IntegerVectors(2,3,min_slope=0).next(a) [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='gale')¶ Returns the binary matrix given by the Gale-Ryser theorem.
The Gale Ryser theorem asserts that if
are two partitions of
of respective lengths
, then there is a binary
matrix
such that
is the vector of row sums and
is the vector of column sums of
, if and only if the conjugate of
dominates
.
INPUT:
p1, p2
– list of integers representing the vectors of row/column sumsalgorithm
– two possible string 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.
Ryser’s Algorithm:
(Ryser [Ryser63]): The construction of an
matrix
, due to Ryser, is described as follows. The construction works if and only if have
.
- Construct the
matrix
from
by defining the
-th row of
to be the vector whose first
entries are
, and the remainder are 0’s,
. This maximal matrix
with row sum
and ones left justified has column sum
.
- Shift the last
in certain rows of
to column
in order to achieve the sum
. Call this
again.
- The
‘s in column n are to appear in those rows in which
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.
- The
- Proceed inductively to construct columns
, ...,
,
.
- Set
. Return
.
EXAMPLES:
Computing the matrix for
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
Or for a non-square matrix with
and
, using Ryser’s algorithm
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 0 1] [1 1 1 0] [0 1 0 0] [1 0 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]
With
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], algorithm = "ryser") [1 0 1 1 0] [1 1 1 0 0] [0 0 0 0 0] [0 0 1 0 0] [1 0 0 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") [1 1 1 0] [0 0 1 0] [0 1 0 0] [1 0 0 0] [1 0 0 0]
TESTS:
This test created a random bipartite graph on
vertices. Its adjacency matrix is binary, and it is used to create some “random-looking” sequences which correspond to an existing matrix. The
gale_ryser_theorem
is then called on these sequences, and the output checked for correctness.:sage: def test_algorithm(algorithm, low = 10, high = 50): ... n,m = randint(low,high), randint(low,high) ... g = graphs.RandomBipartite(n, m, .3) ... s1 = sorted(g.degree([(0,i) for i in range(n)]), reverse = True) ... s2 = sorted(g.degree([(1,i) for i in range(m)]), reverse = True) ... m = gale_ryser_theorem(s1, s2, algorithm = algorithm) ... ss1 = sorted(map(lambda x : sum(x) , m.rows()), reverse = True) ... ss2 = sorted(map(lambda x : sum(x) , m.columns()), reverse = True) ... if ((ss1 != s1) or (ss2 != s2)): ... print "Algorithm %s failed with this input:" % algorithm ... print s1, s2 sage: for algorithm in ["gale", "ryser"]: # long time ... for i in range(50): # long time ... test_algorithm(algorithm, 3, 10) # long time
Null matrix:
sage: gale_ryser_theorem([0,0,0],[0,0,0,0], algorithm="gale") [0 0 0 0] [0 0 0 0] [0 0 0 0] sage: gale_ryser_theorem([0,0,0],[0,0,0,0], algorithm="ryser") [0 0 0 0] [0 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
of dimension
, the vector of row sums is defined as the vector whose
component is equal to the sum of the
row in
. 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
, there exists a binary matrix whose row/colum sums vectors are
and
.
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
( 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
and
are partitions (see the corresponding class
Partition
)If
denote the conjugate of
, the Gale-Ryser theorem asserts that a binary Matrix satisfying the constraints exists if and only if
, where
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 valueand return
. If default is not None, then the function will return the default value for out of range
‘s.
EXAMPLES:
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
sage: f = sage.combinat.integer_vector.list2func([1,2,3], 0) sage: f(2) 3 sage: f(3) 0