Home       Trees       Indices       Help   
Package sage :: Package combinat :: Module integer_list
[hide private]
[frames] | no frames]

Module integer_list

source code


Tools for generating lists of integers in lexicographic order.


Functions [hide private]
 
first(n, min_length, max_length, floor, ceiling, min_slope, max_slope)
Returns the lexicographically smallest valid composition of n satisfying the conditions.		 source code
 
lower_regular(comp, min_slope, max_slope)
Returns the uppest regular composition below comp...		 source code
 
rightmost_pivot(comp, min_length, max_length, floor, ceiling, min_slope, max_slope)
TESTS:...		 source code
 
next(comp, min_length, max_length, floor, ceiling, min_slope, max_slope)
Returns the next integer list after comp that satisfies the contraints.		 source code
 
iterator(n, min_length, max_length, floor, ceiling, min_slope, max_slope)
EXAMPLES:...		 source code
 
list(n, min_length, max_length, floor, ceiling, min_slope, max_slope)
EXAMPLES:...		 source code
 
upper_regular(comp, min_slope, max_slope)
Returns the uppest regular composition above comp.		 source code
 
comp2floor(f, min_slope, max_slope)
Given a composition, returns the lowest regular function N->N above it.		 source code
 
comp2ceil(c, min_slope, max_slope)
Given a composition, returns the lowest regular function N->N below it.		 source code
 
upper_bound(min_length, max_length, floor, ceiling, min_slope, max_slope)
Compute a coarse upper bound on the size of a vector satisfying the constraints.		 source code
 
is_a(comp, min_length, max_length, floor, ceiling, min_slope, max_slope)
Returns True if comp meets the constraints imposed by the arguments.		 source code
Variables [hide private]
  infinity = +Infinity
Function Details [hide private]

first(n, min_length, max_length, floor, ceiling, min_slope, max_slope)

source code  

Returns the lexicographically smallest valid composition of n
satisfying the conditions.

Preconditions:
//  - minslope < maxslope
//  - floor and ceiling need to satisfy the slope constraints
//    e.g. be obtained from comp2floor or comp2ceil
//  - floor must be below ceiling to ensure the existence a
//    valid composition

TESTS:
    sage: import sage.combinat.integer_list as integer_list
    sage: f = lambda l: lambda i: l[i-1]
    sage: f([0,1,2,3,4,5])(1)
    0
    sage: integer_list.first(12, 4, 4, f([0,0,0,0]), f([4,4,4,4]), -1, 1)
    [4, 3, 3, 2]
    sage: integer_list.first(36, 9, 9, f([3,3,3,2,1,1,0,0,0]), f([7,6,5,5,5,5,5,4,4]), -1, 1)
    [7, 6, 5, 5, 4, 3, 3, 2, 1]
    sage: integer_list.first(25, 9, 9, f([3,3,3,2,1,1,0,0,0]), f([7,6,5,5,5,5,5,4,4]), -2, 1)
    [7, 6, 5, 4, 2, 1, 0, 0, 0]
    sage: integer_list.first(36, 9, 9, f([3,3,3,2,1,4,2,0,0]), f([7,6,5,5,5,5,5,4,4]), -2, 1)
    [7, 6, 5, 5, 5, 4, 3, 1, 0]

lower_regular(comp, min_slope, max_slope)

source code  

Returns the uppest regular composition below comp

TESTS:
    sage: import sage.combinat.integer_list as integer_list
    sage: integer_list.lower_regular([4,2,6], -1, 1)
    [3, 2, 3]
    sage: integer_list.lower_regular([4,2,6], -1, infinity)
    [3, 2, 6]
    sage: integer_list.lower_regular([1,4,2], -1, 1)
    [1, 2, 2]
    sage: integer_list.lower_regular([4,2,6,3,7], -2, 1)
    [4, 2, 3, 3, 4]
    sage: integer_list.lower_regular([4,2,infinity,3,7], -2, 1)
    [4, 2, 3, 3, 4]
    sage: integer_list.lower_regular([1, infinity, 2], -1, 1)
    [1, 2, 2]
    sage: integer_list.lower_regular([infinity, 4, 2], -1, 1)
    [4, 3, 2]

rightmost_pivot(comp, min_length, max_length, floor, ceiling, min_slope, max_slope)

source code  


TESTS:
    sage: import sage.combinat.integer_list as integer_list
    sage: f = lambda l: lambda i: l[i-1]
    sage: integer_list.rightmost_pivot([7,6,5,5,4,3,3,2,1], 9, 9, f([3,3,3,2,1,1,0,0,0]), f([7,6,5,5,5,5,5,4,4]), -1, 0)
    [7, 2]
    sage: integer_list.rightmost_pivot([7,6,5,5,4,3,3,2,1], 9, 9,f([3,3,3,2,1,1,0,0,0]), f([7,6,5,5,5,5,5,4,4]), -2, 0)
    [7, 1]
    sage: integer_list.rightmost_pivot([7,6,5,5,4,3,3,2,1], 9, 9,f([3,3,3,2,1,1,0,0,0]), f([7,6,5,5,5,5,5,4,4]), -2, 4)
    [8, 1]
    sage: integer_list.rightmost_pivot([7,6,5,5,4,3,3,2,1], 9, 9,f([3,3,3,2,1,1,0,0,0]), f([7,6,5,5,5,5,5,4,4]), -2, 1)
    [8, 1]
    sage: integer_list.rightmost_pivot([7,6,5,5,5,5,5,4,4], 9, 9,f([3,3,3,2,1,1,0,0,0]), f([7,6,5,5,5,5,5,4,4]), -2, 1)
    sage: integer_list.rightmost_pivot([3,3,3,2,1,1,0,0,0], 9, 9,f([3,3,3,2,1,1,0,0,0]), f([7,6,5,5,5,5,5,4,4]), -2, 1)
    sage: g = lambda x: lambda i: x
    sage: integer_list.rightmost_pivot([1],1,1,g(0),g(2),-10, 10)
    sage: integer_list.rightmost_pivot([1,2],2,2,g(0),g(2),-10, 10)
    sage: integer_list.rightmost_pivot([1,2],2,2,g(1),g(2), -10, 10)
    sage: integer_list.rightmost_pivot([1,2],2,3,g(1),g(2), -10, 10)
    [2, 1]
    sage: integer_list.rightmost_pivot([2,2],2,3,g(2),g(2),-10, 10)
    sage: integer_list.rightmost_pivot([2,3],2,3,g(2),g(2),-10,+10)
    sage: integer_list.rightmost_pivot([3,2],2,3,g(2),g(2),-10,+10)
    sage: integer_list.rightmost_pivot([3,3],2,3,g(2),g(2),-10,+10)
    [1, 2]
    sage: integer_list.rightmost_pivot([6],1,3,g(0),g(6),-1,0)
    [1, 0]
    sage: integer_list.rightmost_pivot([6],1,3,g(0),g(6),-2,0)
    [1, 0]
    sage: integer_list.rightmost_pivot([7,9,8,7],1,5,g(0),g(10),-1,10)
    [2, 6]
    sage: integer_list.rightmost_pivot([7,9,8,7],1,5,g(5),g(10),-10,10)
    [3, 5]
    sage: integer_list.rightmost_pivot([7,9,8,7],1,5,g(5),g(10),-1,10)
    [2, 6]
    sage: integer_list.rightmost_pivot([7,9,8,7],1,5,g(4),g(10),-2,10)
    [3, 7]
    sage: integer_list.rightmost_pivot([9,8,7],1,4,g(4),g(10),-2,0)
    [1, 4]
    sage: integer_list.rightmost_pivot([1,3],1,5,lambda i: i,g(10),-10,10)
    sage: integer_list.rightmost_pivot([1,4],1,5,lambda i: i,g(10),-10,10)
    sage: integer_list.rightmost_pivot([2,4],1,5,lambda i: i,g(10),-10,10)
    [1, 1]

next(comp, min_length, max_length, floor, ceiling, min_slope, max_slope)

source code  

Returns the next integer list after comp that satisfies the contraints.

EXAMPLES:
    sage: from sage.combinat.integer_list import next
    sage: IV = IntegerVectors(2,3,min_slope=0)
    sage: params = IV._parameters()
    sage: next([0,1,1], *params)
    [0, 0, 2]

iterator(n, min_length, max_length, floor, ceiling, min_slope, max_slope)

source code  

EXAMPLES:
    sage: from sage.combinat.integer_list import iterator
    sage: IV = IntegerVectors(2,3,min_slope=0)
    sage: params = IV._parameters()
    sage: list(iterator(2,*params))
    [[0, 1, 1], [0, 0, 2]]

list(n, min_length, max_length, floor, ceiling, min_slope, max_slope)

source code  

EXAMPLES:
    sage: import sage.combinat.integer_list as integer_list
    sage: g = lambda x: lambda i: x
    sage: integer_list.list(0,0,infinity,g(1),g(infinity),0,infinity)
    [[]]
    sage: integer_list.list(0,0,infinity,g(1),g(infinity),0,0)
    [[]]
    sage: integer_list.list(0, 0, 0, g(1), g(infinity), 0, 0)
    [[]]
    sage: integer_list.list(0, 0, 0, g(0), g(infinity), 0, 0)
    [[]]
    sage: integer_list.list(0, 0, infinity, g(1), g(infinity), 0, infinity)
    [[]]
    sage: integer_list.list(1, 0, infinity, g(1), g(infinity), 0, infinity)
    [[1]]
    sage: integer_list.list(0, 1, infinity, g(1), g(infinity), 0, infinity)
    []
    sage: integer_list.list(0, 1, infinity, g(0), g(infinity), 0, infinity)
    [[0]]
    sage: integer_list.list(3, 0, 2, g(0), g(infinity), -infinity, infinity)
    [[3], [2, 1], [1, 2], [0, 3]]
    sage: partitions = (0, infinity, g(0), g(infinity), -infinity, 0)
    sage: partitions_min_2 = (0, infinity, g(2), g(infinity), -infinity, 0)
    sage: compositions = (0, infinity, g(1), g(infinity), -infinity, infinity)
    sage: integer_vectors = lambda l: (l, l, g(0), g(infinity), -infinity, infinity)
    sage: lower_monomials = lambda c: (len(c), len(c), g(0), lambda i: c[i], -infinity, infinity)
    sage: upper_monomials = lambda c: (len(c), len(c), g(0), lambda i: c[i], -infinity, infinity)
    sage: constraints = (0, infinity, g(1), g(infinity), -1, 0)
    sage: integer_list.list(6, *partitions)
    [[6],
     [5, 1],
     [4, 2],
     [4, 1, 1],
     [3, 3],
     [3, 2, 1],
     [3, 1, 1, 1],
     [2, 2, 2],
     [2, 2, 1, 1],
     [2, 1, 1, 1, 1],
     [1, 1, 1, 1, 1, 1]]
    sage: integer_list.list(6, *constraints)
    [[6],
     [3, 3],
     [3, 2, 1],
     [2, 2, 2],
     [2, 2, 1, 1],
     [2, 1, 1, 1, 1],
     [1, 1, 1, 1, 1, 1]]
    sage: integer_list.list(1, *partitions_min_2)
    []
    sage: integer_list.list(2, *partitions_min_2)
    [[2]]
    sage: integer_list.list(3, *partitions_min_2)
    [[3]]
    sage: integer_list.list(4, *partitions_min_2)
    [[4], [2, 2]]
    sage: integer_list.list(5, *partitions_min_2)
    [[5], [3, 2]]
    sage: integer_list.list(6, *partitions_min_2)
    [[6], [4, 2], [3, 3], [2, 2, 2]]
    sage: integer_list.list(7, *partitions_min_2)
    [[7], [5, 2], [4, 3], [3, 2, 2]]
    sage: integer_list.list(9, *partitions_min_2)
    [[9], [7, 2], [6, 3], [5, 4], [5, 2, 2], [4, 3, 2], [3, 3, 3], [3, 2, 2, 2]]
    sage: integer_list.list(10, *partitions_min_2)
    [[10],
     [8, 2],
     [7, 3],
     [6, 4],
     [6, 2, 2],
     [5, 5],
     [5, 3, 2],
     [4, 4, 2],
     [4, 3, 3],
     [4, 2, 2, 2],
     [3, 3, 2, 2],
     [2, 2, 2, 2, 2]]
    sage: integer_list.list(4, *compositions)
    [[4], [3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]

upper_regular(comp, min_slope, max_slope)

source code  

Returns the uppest regular composition above comp.

TESTS:
    sage: import sage.combinat.integer_list as integer_list
    sage: integer_list.upper_regular([4,2,6],-1,1)
    [4, 5, 6]
    sage: integer_list.upper_regular([4,2,6],-2, 1)
    [4, 5, 6]
    sage: integer_list.upper_regular([4,2,6,3,7],-2, 1)
    [4, 5, 6, 6, 7]
    sage: integer_list.upper_regular([4,2,6,1], -2, 1)
    [4, 5, 6, 4]

comp2floor(f, min_slope, max_slope)

source code  

Given a composition, returns the lowest regular function N->N above
it.

EXAMPLES:
    sage: from sage.combinat.integer_list import comp2floor
    sage: f = comp2floor([2, 1, 1],-1,0)
    sage: [f(i) for i in range(10)]
    [2, 1, 1, 1, 2, 3, 4, 5, 6, 7]

comp2ceil(c, min_slope, max_slope)

source code  

Given a composition, returns the lowest regular function N->N below
it.

EXAMPLES:
    sage: from sage.combinat.integer_list import comp2ceil
    sage: f = comp2ceil([2, 1, 1],-1,0)
    sage: [f(i) for i in range(10)]
    [2, 1, 1, 1, 2, 3, 4, 5, 6, 7]

upper_bound(min_length, max_length, floor, ceiling, min_slope, max_slope)

source code  

Compute a coarse upper bound on the size of a vector satisfying
the constraints.

TESTS:
    sage: import sage.combinat.integer_list as integer_list
    sage: f = lambda x: lambda i: x
    sage: integer_list.upper_bound(0,4,f(0), f(1),-infinity,infinity)
    4
    sage: integer_list.upper_bound(0, infinity, f(0), f(1), -infinity, infinity)
    +Infinity
    sage: integer_list.upper_bound(0, infinity, f(0), f(1), -infinity, -1)
    1
    sage: integer_list.upper_bound(0, infinity, f(0), f(5), -infinity, -1)
    15
    sage: integer_list.upper_bound(0, infinity, f(0), f(5), -infinity, -2)
    9

is_a(comp, min_length, max_length, floor, ceiling, min_slope, max_slope)

source code  

Returns True if comp meets the constraints imposed by the arguments.

EXAMPLES:
    sage: from sage.combinat.integer_list import is_a
    sage: IV = IntegerVectors(2,3,min_slope=0)
    sage: params = IV._parameters()
    sage: all([is_a(iv, *params) for iv in IV])
    True

   Home       Trees       Indices       Help   
Generated by Epydoc 3.0beta1 on Thu Jul 17 04:23:25 2008 http://epydoc.sourceforge.net