uconf.sampling

Random basis element sampling without full basis enumeration.

Provides construction-aware utilities to generate random basis elements for the various algebraic objects in the configuration model pipeline. Each sampler exploits the combinatorial structure of its parent object (tree shape, vertex decorations, factor products) to generate random elements directly, without materializing the full basis first.

Construction-aware samplers:

• random_surjection() — random surjection via rejection sampling.

• random_planar_surjection() — random planar surjection.

• random_sphere_admissible_surjection() — sphere-admissible surjection via direct construction.

• random_lie_key() — random Lie-operad basis key.

• random_barratt_eccles_key() — random Barratt–Eccles key.

• random_hadamard_key() — random Hadamard-product basis key by sampling factors independently.

• random_shuffle_tree() — random decorated shuffle tree (used internally by bar/cobar construction samplers).

• random_bar_element() — random bar construction element.

• random_cobar_element() — random cobar construction element.

• random_free_algebra_element() — random free algebra element by sampling operad key and module tuple independently.

• random_cofree_coalgebra_element() — random cofree coalgebra element by sampling cooperad key and module tuple independently.

• random_tree_module_element() — random tree-module element.

• sample_basis() — sample k random elements from any parent, dispatching to construction-aware generators when available and falling back to basis enumeration otherwise.

• sample_operad_basis() — sample operad/cooperad basis elements.

• sample_algebra_pool() — replacement for _build_algebra_pool in tests.

• sphere_nontrivial_surjection_iter() — iterate over surjections that act nontrivially on the sphere.

uconf.sampling.random_surjection_key(n, degree, rng)

Generate a random valid surjection key of arity n and degree degree.

A surjection of arity n and degree d is a tuple of length n + d with values in {1, …, n} that is surjective and has no consecutive equal entries.

Uses rejection sampling: generate a random tuple and check validity. Returns None if no valid surjection is found after a limited number of attempts (unlikely for small n and d).

Parameters:

• n (int)

• degree (int)

• rng (Random)

Return type:

tuple[int, …] | None

uconf.sampling.random_surjection(n, degree, base_ring, rng)

Generate a random Surjection element of arity n and degree degree.

Returns a single-term element or None if sampling fails.

Parameters:

• n (int)

• degree (int)

• rng (Random)

uconf.sampling.random_planar_surjection_key(n, degree, rng)

Generate a random planar surjection key of arity n and degree degree.

A surjection is planar when the first occurrences of 1, 2, …, n appear in increasing order of position.

Uses rejection sampling with planarity filter.

Parameters:

• n (int)

• degree (int)

• rng (Random)

Return type:

tuple[int, …] | None

uconf.sampling.random_planar_surjection(n, degree, base_ring, rng)

Generate a random planar Surjection element.

Parameters:

• n (int)

• degree (int)

• rng (Random)

uconf.sampling.random_sphere_admissible_surjection_key(n, dim, rng)

Generate a random sphere-admissible surjection key.

A surjection of arity n is sphere-admissible for S^d (d = dim) when its degree equals d(n−1) and it decomposes as the concatenation of d + 1 permutations of {1, …, n} with overlapping endpoints.

Direct construction: generate d + 1 random permutations σ_1, …, σ_{d+1} of {1, …, n} with the overlap constraint σ_j(n) = σ_{j+1}(1).

Parameters:

• n (int)

• dim (int)

• rng (Random)

Return type:

tuple[int, …] | None

uconf.sampling.random_sphere_admissible_surjection(n, dim, base_ring, rng)

Generate a random sphere-admissible Surjection element.

Parameters:

• n (int)

• dim (int)

• rng (Random)

uconf.sampling.sphere_nontrivial_surjection_iter(n, dim, base_ring)

Iterate over surjections of arity n that act nontrivially on S^d.

Only surjections of degree d(n−1) with the sphere-admissible concatenation form are considered. Yields (key, sign) pairs.

Parameters:

• n (int)

• dim (int)

Return type:

Iterator

uconf.sampling.sphere_nontrivial_operad_basis_iter(operad_cls, n, dim, base_ring)

Iterate over operad basis elements at arity n whose surjection factor acts nontrivially on S^d.

Works for HadamardProduct(_, Surjection) and plain Surjection. For non-Hadamard operads, falls back to the full basis at degree d(n-1).

Parameters:

• n (int)

• dim (int)

Return type:

Iterator

uconf.sampling.random_lie_key(n, rng)

Return a random Lie basis key at arity n.

Lie basis keys are permutations of (1, …, n−1) (Lyndon/PBW basis).

Parameters:

• n (int)

• rng (Random)

Return type:

tuple[int, …]

uconf.sampling.random_lie_element(n, base_ring, rng)

Generate a random Lie operad basis element at arity n.

Parameters:

• n (int)

• rng (Random)

uconf.sampling.random_barratt_eccles_key(n, degree, rng)

Generate a random Barratt–Eccles basis key of arity n and degree degree.

A BE key is a tuple of degree + 1 permutations in S_n with no consecutive equal permutations. Uses direct construction with rejection for the no-consecutive-repeat constraint.

Returns None if degree < 0 or sampling fails.

Parameters:

• n (int)

• degree (int)

• rng (Random)

Return type:

tuple | None

uconf.sampling.random_barratt_eccles_element(n, degree, base_ring, rng)

Generate a random Barratt–Eccles element of arity n and degree degree.

Returns a single-term element or None if sampling fails.

Parameters:

• n (int)

• degree (int)

• rng (Random)

uconf.sampling.random_hadamard_key(hadamard_parent, degree, rng, *, sphere_nontrivial=False, sphere_dim=None)

Generate a random basis key for a Hadamard product component.

Samples left and right factors independently at compatible degrees, without materializing either factor’s full basis.

Parameters

hadamard_parentHadamardProduct.Component

The Hadamard-product component.

degreeint

Target total degree.

rngRandom

Random number generator.

sphere_nontrivialbool

If True, only sample right-factor (Surjection) elements that act nontrivially on S^{sphere_dim}.

sphere_dimint or None

Required when sphere_nontrivial=True.

Returns

Element or None

A random Hadamard product element, or None if sampling failed.

Parameters:

• degree (int)

• rng (Random)

• sphere_nontrivial (bool)

• sphere_dim (int | None)

Return type:

Any | None

uconf.sampling.sample_hadamard_basis(hadamard_parent, degree, k, rng, *, sphere_nontrivial=False, sphere_dim=None)

Sample up to k random Hadamard-product basis elements.

If fewer than k distinct elements can be generated, returns all that were found.

Parameters:

• degree (int)

• k (int)

• rng (Random)

• sphere_nontrivial (bool)

• sphere_dim (int | None)

Return type:

list

uconf.sampling.random_shuffle_tree(leaf_set, max_weight, operad_cls, base_ring, target_degree, vertex_offset, rng, *, max_attempts=200, sphere_nontrivial=False, sphere_dim=None)

Generate a random decorated shuffle tree.

Constructs trees top-down: at each internal vertex, randomly choose the vertex arity, a random decoration from the operad/cooperad, and a random partition of the leaves. Recurse into each child subtree.

The vertex_offset parameter selects the degree convention:

• +1: bar degree Σ (deg_P(v) + 1).

• -1: cobar degree Σ (deg_C(v) - 1).

• 0: free/cofree degree Σ deg(v).

Returns a decorated RootedTree or None if sampling fails.

Parameters:

• leaf_set (tuple)

• max_weight (int)

• target_degree (int)

• vertex_offset (int)

• rng (Random)

• max_attempts (int)

• sphere_nontrivial (bool)

• sphere_dim (int | None)

uconf.sampling.random_bar_element(parent, degree, rng, *, sphere_nontrivial=False, sphere_dim=None)

Generate a random bar construction element without materializing the full basis.

Parameters

parentBarConstruction.Component

The bar construction component.

degreeint

Target bar degree.

rngRandom

Random number generator.

sphere_nontrivialbool

If True, only generate surjection factors that act nontrivially on S^{sphere_dim}.

sphere_dimint or None

Required when sphere_nontrivial=True.

Returns

Element or None

A random bar construction element.

Parameters:

• degree (int)

• rng (Random)

• sphere_nontrivial (bool)

• sphere_dim (int | None)

uconf.sampling.random_cobar_element(parent, degree, rng, *, sphere_nontrivial=False, sphere_dim=None)

Generate a random cobar construction element without materializing the full basis.

Parameters

parentCobarConstruction.Component

The cobar construction component.

degreeint

Target cobar degree.

rngRandom

Random number generator.

sphere_nontrivialbool

If True, only generate surjection factors that act nontrivially on S^{sphere_dim}.

sphere_dimint or None

Required when sphere_nontrivial=True.

Returns

Element or None

A random cobar construction element.

Parameters:

• degree (int)

• rng (Random)

• sphere_nontrivial (bool)

• sphere_dim (int | None)

uconf.sampling.random_free_algebra_element(parent, degree, rng, *, weight=None, sphere_nontrivial=False, sphere_dim=None)

Generate a random free algebra element without materializing the full basis.

For P ∘ M, samples a random arity n, a random planar operad element from P(n), and a random n-tuple of module basis keys.

Parameters

parentFreeAlgebraModule

The free algebra module.

degreeint

Target total degree.

rngRandom

Random number generator.

weightint or None

If given, restrict to elements of this weight.

sphere_nontrivialbool

If True, only generate surjection factors that act nontrivially on S^{sphere_dim}.

sphere_dimint or None

Required when sphere_nontrivial=True.

Returns

Element or None

Parameters:

• degree (int)

• rng (Random)

• weight (int | None)

• sphere_nontrivial (bool)

• sphere_dim (int | None)

uconf.sampling.random_cofree_coalgebra_element(parent, degree, rng, *, weight=None, sphere_nontrivial=False, sphere_dim=None)

Generate a random cofree coalgebra element without materializing the full basis.

For C ∘ M, samples a random arity n, a random planar cooperad element from C(n), and a random n-tuple of module basis keys.

Parameters

parentCofreeCoalgebraModule

The cofree coalgebra module.

degreeint

Target total degree.

rngRandom

Random number generator.

weightint or None

If given, restrict to elements of this weight.

sphere_nontrivialbool

If True, only generate surjection factors that act nontrivially on S^{sphere_dim}.

sphere_dimint or None

Required when sphere_nontrivial=True.

Returns

Element or None

Parameters:

• degree (int)

• rng (Random)

• weight (int | None)

• sphere_nontrivial (bool)

• sphere_dim (int | None)

uconf.sampling.random_tree_module_element(parent, degree, rng, *, weight=None, sphere_nontrivial=False, sphere_dim=None)

Generate a random tree-module element without materializing the full basis.

For tree-decorated composites S ∘ M, generates a random decorated tree with random module elements at the leaves.

Parameters

parentTreeModule

The tree module.

degreeint

Target total degree.

rngRandom

Random number generator.

weightint or None

If given, restrict to elements of this weight.

sphere_nontrivialbool

If True, only generate surjection factors that act nontrivially on S^{sphere_dim}.

sphere_dimint or None

Required when sphere_nontrivial=True.

Returns

Element or None

Parameters:

• degree (int)

• rng (Random)

• weight (int | None)

• sphere_nontrivial (bool)

• sphere_dim (int | None)

uconf.sampling.sample_basis(parent, degree, k, rng, *, weight=None, sphere_nontrivial=False, sphere_dim=None)

Sample up to k random basis elements from parent at degree degree.

Dispatches to construction-aware generators when the parent type is recognized (bar/cobar constructions, free/cofree algebras, Hadamard products, etc.). Falls back to graded_basis/basis_iter enumeration when no direct sampler is available.

Parameters

parent

A SageMath parent with graded_basis(d) or basis_iter(d).

degreeint

Homological degree.

kint

Maximum number of elements to return.

rngRandom

Random number generator.

weightint or None

If given, restrict to elements of this weight (uses graded_basis_by_weight).

sphere_nontrivialbool

If True, only generate surjection factors that act nontrivially on S^{sphere_dim}. Propagated recursively through all constructions.

sphere_dimint or None

Required when sphere_nontrivial=True.

Parameters:

• degree (int)

• k (int)

• rng (Random)

• weight (int | None)

• sphere_nontrivial (bool)

• sphere_dim (int | None)

Return type:

list

uconf.sampling.sample_operad_basis(operad_cls, n, degree, k, base_ring, rng, *, sphere_nontrivial=False, sphere_dim=None)

Sample up to k operad basis elements at arity n and degree degree.

Parameters

operad_cls

Operad factory (e.g. Surjection, HadamardProduct factory, etc.).

nint

Arity.

degreeint

Degree.

kint

Maximum number of elements.

base_ring

Coefficient ring.

rngRandom

Random number generator.

sphere_nontrivialbool

If True, only return elements whose surjection factor acts nontrivially on the sphere.

sphere_dimint or None

Required when sphere_nontrivial=True.

Parameters:

• n (int)

• degree (int)

• k (int)

• rng (Random)

• sphere_nontrivial (bool)

• sphere_dim (int | None)

Return type:

list

uconf.sampling.sample_algebra_pool(mod, k_per_bucket, rng, *, weights=(1, 2), deg_range=range(-1, 6))

Sample algebra elements across multiple weight/degree buckets.

Replacement for the test helper _build_algebra_pool. Uses construction-aware sampling to avoid materializing the full basis.

Parameters

mod

Algebra module with graded_basis_by_weight(d, w).

k_per_bucketint

Maximum elements per (degree, weight) cell.

rngRandom

Random number generator.

weightstuple[int, …]

Weights to sample.

deg_rangerange

Degree range to sample.

Parameters:

• k_per_bucket (int)

• rng (Random)

• weights (tuple[int, ...])

• deg_range (range)

Return type:

list