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