Combinatorics¶
Combinatorics methods
EXEMPLES:
sage: from slabbe.combinat import random_composition
sage: c = random_composition(24,9)
sage: c # random
[1, 4, 2, 2, 3, 5, 4, 2, 1]
sage: from slabbe.combinat import random_simplex_point
sage: random_simplex_point(3) # random
[0.2493321790694003, 0.5353600549544871, 0.21530776597611256]
sage: from slabbe.combinat import random_interior_point
sage: p = polytopes.hypercube(3)
sage: p = p + vector([20,0,0])
sage: random_interior_point(p) # random
(19.33174562788114, -0.5428002756082744, -0.3568284089832092)
- slabbe.combinat.integral_points_count_union_of_polytopes(L)¶
Return the cardinality of an union of polytopes.
See https://en.wikipedia.org/wiki/Inclusion–exclusion_principle
INPUT:
L
– list of polytopes
EXEMPLES:
sage: P = Polyhedron(ieqs=[[0,1,0],[0,0,1],[9,-1,0],[9,0,-1]]) sage: Q = Polyhedron(ieqs=[[-5,1,0],[-5,0,1],[14,-1,0],[14,0,-1]]) sage: P.integral_points_count() # optional -- latte_int 100 sage: Q.integral_points_count() # optional -- latte_int 100 sage: from slabbe.combinat import integral_points_count_union_of_polytopes sage: integral_points_count_union_of_polytopes([P,Q]) # optional -- latte_int 175
- slabbe.combinat.intersection_of_polytopes(L)¶
Return the intersection of a list of polytopes.
INPUT:
L
– list of polytopes
EXEMPLES:
sage: from slabbe.combinat import intersection_of_polytopes sage: P = Polyhedron(ieqs=[[0,1,0],[0,0,1],[9,-1,0],[9,0,-1]]) sage: Q = Polyhedron(ieqs=[[-5,1,0],[-5,0,1],[14,-1,0],[14,0,-1]]) sage: I = intersection_of_polytopes([P,Q]) sage: I A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: I.integral_points_count() # optional -- latte_int 25
TESTS:
sage: intersection_of_polytopes(iter([P,Q])) A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: intersection_of_polytopes(iter([])) Traceback (most recent call last): ... NotImplementedError: intersection of an empty list of polytopes not defined
- slabbe.combinat.non_uniform_randint(L)¶
Return a random integer from 0 to len(L)-1 with probabilities proportional to the (integral) entries of L.
INPUT:
L
– list of integers
EXEMPLES:
sage: from slabbe.combinat import non_uniform_randint sage: non_uniform_randint([2,3,5]) # random 1 sage: non_uniform_randint([2,3,5]) # random 2 sage: non_uniform_randint([2,3,5]) # random 2 sage: from collections import Counter sage: L = [non_uniform_randint([2,3,5]) for _ in range(100000)] sage: Counter(L) # random Counter({2: 49805, 1: 30228, 0: 19967})
- slabbe.combinat.random()¶
random() -> x in the interval [0, 1).
- slabbe.combinat.random_composition(n, length)¶
EXEMPLES:
sage: from slabbe.combinat import random_composition sage: random_composition(4,2) # random [1, 3] sage: random_composition(4,2) # random [2, 2] sage: random_composition(4,2) # random [3, 1] sage: c = random_composition(24,9) sage: c # random [1, 4, 2, 2, 3, 5, 4, 2, 1] sage: sum(c) 24
Because this is very slow!!:
sage: C = Compositions(24, length=9) sage: %time C.random_element() # not tested CPU times: user 43.3 s, sys: 31.9 ms, total: 43.3 s Wall time: 43.2 s [2, 2, 5, 2, 8, 1, 1, 2, 1]
- slabbe.combinat.random_interior_point(self, a=10, integer=False)¶
Return a random interior point of a polytope.
INPUT:
a
– number, amplitude of random deplacement in the direction of each ray.integer
– bool, whether the output must be with integer coordinates
EXEMPLES:
sage: from slabbe.combinat import random_interior_point sage: p = polytopes.hypercube(3) sage: p = p + vector([20,0,0]) sage: p.center() (20, 0, 0) sage: random_interior_point(p) # random (19.33174562788114, -0.5428002756082744, -0.3568284089832092) sage: random_interior_point(p) # random (20.039169786976075, -0.4121594862234468, -0.05623023234688396) sage: random_interior_point(p, integer=True) # random (21, 0, 0)
- slabbe.combinat.random_interior_point_compact_polytope(self, uniform='simplex', integer=False)¶
Return a random interior point of a compact polytope.
INPUT:
uniform
–'points'
(slow) or'simplex'
(fast), whether to take the probability uniformly with respect to the set of integral points or with respect to the simplexes.integer
– bool, whether the output must be with integer coordinates
EXEMPLES:
sage: from slabbe.combinat import random_interior_point_compact_polytope sage: p = polytopes.hypercube(3) sage: p = p + vector([30,20,10]) sage: p.center() (30, 20, 10) sage: random_interior_point_compact_polytope(p) # random (19.33174562788114, -0.5428002756082744, -0.3568284089832092) sage: random_interior_point_compact_polytope(p) # random (20.039169786976075, -0.4121594862234468, -0.05623023234688396) sage: random_interior_point_compact_polytope(p, integer=True) # random (30, 19, 9)
- slabbe.combinat.random_interior_point_simplex(self, integer=False)¶
Return a random interior point of a simplex.
This method was based on the code
P.center()
of sage.INPUT:
integer
– bool, whether the output must be with integer coordinates
EXEMPLES:
sage: from slabbe.combinat import random_interior_point_simplex sage: P = 10 * polytopes.simplex(3) sage: random_interior_point_simplex(P) # random (2.8787864522849462, 5.302173919578364, 1.7059355910006113, 0.11310403713607808) sage: a = random_interior_point_simplex(P, integer=True) sage: a # random (0, 7, 1, 2) sage: a in P True
- slabbe.combinat.random_simplex_point(d)¶
Return a random vector of d positive real numbers summing to 1.
INPUT:
d
– integer
EXEMPLES:
sage: from slabbe.combinat import random_simplex_point sage: random_simplex_point(7) # random [0.06137280030263492, 0.08066113584919432, 0.09019666554921013, 0.24473802319989957, 0.41761622259683495, 0.10043545384643937, 0.004979698655786735] sage: random_simplex_point(2) # random [0.5677654878488222, 0.4322345121511778] sage: random_simplex_point(3) # random [0.2493321790694003, 0.5353600549544871, 0.21530776597611256]
TESTS:
sage: sum(random_simplex_point(4)) 1.0 sage: sum(random_simplex_point(7)) 1.0