enumerate and count_inequivalent

enumerate(parent::ParentLattice{D}, sites::Sites{D};
          supercells::SupercellSelection,
          concentration::Union{Nothing, Concentration, ConcentrationRange} = nothing,
          algorithm::Symbol = :auto,
          memory_budget::Int = default_memory_budget(),
          on_overflow::Symbol = :error,
          partition_threshold::Int = 100,
          on_partition_overflow::Symbol = :error,
          include_superperiodic::Bool = false,
          skip_resource_check::Bool = false) -> Enumeration{D, Vector{Int8}}

Enumerate symmetry-inequivalent derivative structures of parent decorated by labelings drawn from sites.allowed_labels, over the supercells specified by supercells, optionally constrained to a fixed concentration or ConcentrationRange.

Algorithm dispatch

• algorithm = :auto (default): the tree (:recursive_stabilizer) for almost everything — including unrestricted enumeration, where :auto synthesizes a full-range ConcentrationRange internally (bench Section 5 shows ~2-3× speedup and ~half the memory vs the bitmap). With concentration supplied, picks between :multinomial and :recursive_stabilizer by predicted memory; for Regime C, picks :recursive_stabilizer. Falls through to :exhaustive only for the (unsupported) "Regime C unrestricted" case so the validation error fires.
• algorithm = :exhaustive (Hart-Forcade 2008): unrestricted enumeration via the k^n bitmap; ignores concentration if supplied. Not :auto's default — use it explicitly for the bitmap's memory profile or to cross-check the tree.
• algorithm = :multinomial (Hart-Forcade 2012): fixed-concentration enumeration via the multinomial-hash crossing-out. Requires concentration !== nothing; Regime A and Regime B only.
• algorithm = :multinomial_restricted (HF 2012 §A.1): the bitmap variant with a site-mask filter, for heterogeneous sublattices (Regime C — perovskite, half/full Heusler, wurtzite, zinc-blende, etc.). Requires concentration !== nothing.
• algorithm = :recursive_stabilizer (Morgan 2017): tree-search-with-shrinking-stabilizers; streams (no bitmap) and beats the bitmap algorithms in nearly every measured case. :auto's default for both unrestricted and fixed-concentration when the bitmap doesn't fit (or always, for Regime C).

Concentration handling

• concentration === nothing → unrestricted.
• concentration::Concentration → single fixed concentration; the multinomial-hash algorithm enumerates the exactly-a_i-of-each-species labelings.
• concentration::ConcentrationRange → loops over concentrations_in_range(cr, n) for each supercell volume; gates against partition explosion via partition_threshold (default 100).

Super-periodicity policy

include_superperiodic = false (default) drops colorings whose true period strictly divides the supercell — these are duplicates of smaller-supercell derivatives across a volume sweep (HF 2008 step 5d). include_superperiodic = true keeps them and returns the full Burnside orbit space; useful for theoretical comparisons or single-volume queries where the user wants every orbit.

Returns

Enumeration{D, Vector{Int8}} containing the parent, sites, list of distinct supercells encountered, and the enumerated structures. Iterable + indexable.

Examples

Setup used in all examples below — FCC primitive, one binary substitution site:

julia> p = ParentLattice([0.0 0.5 0.5; 0.5 0.0 0.5; 0.5 0.5 0.0]);

julia> sites = Sites([Site([0.0, 0.0, 0.0], [0, 1])]);

Unrestricted enumeration (no concentration): all 19 symmetry-inequivalent binary FCC structures at supercell volume 4.

julia> e = enumerate(p, sites; supercells = VolumeRange(4:4));

julia> length(e)
19

julia> to_labeling(e[1])
4-element Vector{Int8}:
 0
 1
 1
 1

Fixed concentration via concentration_count: the canonical HF 2012 FCC binary 4:4 at n=8 → 94 structures.

julia> c = concentration_count([4, 4]; n_total = 8);

julia> e = enumerate(p, sites; supercells = VolumeRange(8:8), concentration = c);

julia> length(e)
94

Concentration range restricting the first species to 1..2 of 12 atoms — illustrates ConcentrationRange's natural use (sparse / dilute regime). The two partitions (1,11) and (2,10) together yield 216 structures at n=12.

julia> cr = ConcentrationRange([(1//12, 2//12), (10//12, 11//12)]);

julia> e = enumerate(p, sites; supercells = VolumeRange(12:12), concentration = cr);

julia> length(e)
216

Explicit algorithm — :recursive_stabilizer (Morgan 2017) on the same fixed-concentration case as before. Returns the same 94 structures; the algorithm-equivalence guarantee.

julia> e = enumerate(p, sites; supercells = VolumeRange(8:8), concentration = c,
                     algorithm = :recursive_stabilizer);

julia> length(e)
94

Enumeration{D,L}

The output of enumerate(parent, sites; supercells, ...). Holds the full result of an enumeration call: the parent lattice, the sites description, the list of distinct supercells encountered (shared across structures by index), and the structures themselves.

Enumeration is iterable and indexable:

e = enumerate(parent, sites; supercells = VolumeRange(2:6))
for s in e
    digits = to_labeling(s)
    # ...
end
n = length(e)
first = e[1]

The structures vector is fully materialized at construction (eager).

EnumeratedStructure{D,L}

A single enumerated derivative structure: a reference to a Supercell{D} (by index into the parent Enumeration.supercells vector) plus the labeling that decorates it.

The parametric L is the labeling representation (the "string" of atom types). Currently only L = Vector{Int8} is supported — the decoded form, ~n bytes per structure.

The orbit_size field is the symmetry-orbit size of the labeling under the supercell's permutation group G — i.e., |G| / |Stab(labeling)|, via the orbit-stabilizer theorem. This is UNCLE's d_F (HF 2008 Eq. 3) and matches the Fortran enumlib's lab_degen field. Downstream consumers use it for free-energy weighting in MC simulations, convex-hull degeneracy display, and phase-space coverage diagnostics.

Examples

julia> p = ParentLattice([0.0 0.5 0.5; 0.5 0.0 0.5; 0.5 0.5 0.0]);

julia> sites = Sites([Site([0.0, 0.0, 0.0], [0, 1])]);

julia> e = enumerate(p, sites; supercells = VolumeRange(2:2),
                     concentration = concentration_count([1, 1]; n_total = 2));

julia> e[1].orbit_size            # the only orbit at this concentration has size |G|/|Stab|
2

to_labeling(s::EnumeratedStructure) -> Vector{Int8}

Return the labeling of structure s as a Vector{Int8}. For the L = Vector{Int8} representation this is a no-op pass-through.

Examples

Small case — FCC binary at volume 2 (the first structure of two):

julia> p = ParentLattice([0.0 0.5 0.5; 0.5 0.0 0.5; 0.5 0.5 0.0]);

julia> sites = Sites([Site([0.0, 0.0, 0.0], [0, 1])]);

julia> e = enumerate(p, sites; supercells = VolumeRange(2:2));

julia> to_labeling(e[1])
2-element Vector{Int8}:
 0
 1

Larger case — BCC binary at volume 8 with 4:4 concentration (94 structures total), the 7th:

julia> A_bcc = 0.5 * [-1.0 1.0 1.0; 1.0 -1.0 1.0; 1.0 1.0 -1.0];

julia> p = ParentLattice(A_bcc);

julia> sites = Sites([Site([0.0, 0.0, 0.0], [0, 1])]);

julia> e = enumerate(p, sites; supercells = VolumeRange(8:8),
                     concentration = concentration_count([4, 4]; n_total = 8));

julia> to_labeling(e[7])
8-element Vector{Int8}:
 0
 0
 0
 0
 1
 1
 1
 1

default_memory_budget()

The default memory_budget for enumerate(...) — adapts to the host machine. 25% of the system's physical memory, with a 2 GiB floor.

Caveat: Sys.total_memory() reports the machine's RAM, not the cgroup / Slurm / Kubernetes allocation in containerized environments. HPC users on a shared cluster need to pass memory_budget = $SLURM_MEM_PER_NODE (or similar) explicitly.

count_inequivalent(parent::ParentLattice{D}, sites::Sites{D};
                   supercells::SupercellSelection,
                   concentration = nothing,
                   include_superperiodic::Bool = false,
                   breakdown::Bool = false) -> BigInt or InequivalentCount{D}

Count symmetry-inequivalent derivative structures without enumerating them. Pólya / Burnside-averaged orbit count.

• include_superperiodic = false (default): primitive (aperiodic) count via Möbius inversion. Matches length(enumerate(parent, sites; ..., include_superperiodic = false)).
• include_superperiodic = true: full Burnside orbit count, super-periodic included. Matches length(enumerate(parent, sites; ..., include_superperiodic = true)).
• breakdown = false (default) returns the BigInt total.
• breakdown = true returns InequivalentCount{D} with per-volume / per-concentration / per-HNF breakdowns.

Heterogeneous Sites (per-site allowed_labels — zinc-blende, half/full-Heusler, perovskite, or any site pinned to one species) are counted with the label-restricted Pólya formulas, which intersect allowed_labels across each orbit. Uniform Sites keep the scalar-k fast path.

An unconstrained ConcentrationRange (every species free over [0, 1], as read_struct_enum_in synthesizes for full mode) is treated as no concentration constraint at all — exact, since every coloring has one concentration, and far cheaper than iterating every composition. Consequence: in that case the returned by_concentration is empty, because materializing it would mean enumerating every composition of the site count. Pass a narrower ConcentrationRange if you need that breakdown.

Cost: O(|G| · n) per supercell for the unrestricted case; with Möbius correction add subgroup-enumeration of T (cheap at typical supercell sizes). Sub-second across the full reference corpus.

See research.md §5.2.1 for the super-periodicity policy and research.md §4.6 / §7.2 for the underlying Pólya machinery.

Examples

Setup — FCC binary, one substitution site:

julia> p = ParentLattice([0.0 0.5 0.5; 0.5 0.0 0.5; 0.5 0.5 0.0]);

julia> sites = Sites([Site([0.0, 0.0, 0.0], [0, 1])]);

Basic count — the canonical FCC binary n=12 unrestricted total:

julia> count_inequivalent(p, sites; supercells = VolumeRange(12:12))
7140

Include super-periodics — adds the 745 super-periodic orbits that the default policy drops (HF 2008 step 5d). Matches length(enumerate(...; include_superperiodic = true)).

julia> count_inequivalent(p, sites; supercells = VolumeRange(12:12), include_superperiodic = true)
7885

Breakdown over a volume range — breakdown = true returns an InequivalentCount; by_volume is a sorted Vector{Tuple{Int, BigInt}} so indexing is deterministic.

julia> ic = count_inequivalent(p, sites; supercells = VolumeRange(8:12), breakdown = true);

julia> ic.total
10609

julia> ic.by_volume[1]   # smallest volume in the range
(8, 390)

julia> ic.by_volume[end] # largest
(12, 7140)

InequivalentCount{D}

Structured return of count_inequivalent(...; breakdown = true). Total count plus per-supercell breakdown so the user can see "where my structures come from."

Fields:

• total::BigInt — sum across the request.
• by_volume::Vector{Tuple{Int, BigInt}} — (n, count_at_n) pairs, in volume order.
• by_concentration::Vector{Tuple{Concentration, BigInt}} — populated when concentration was a ConcentrationRange; one entry per partition. Empty otherwise.
• by_hnf::Vector{Tuple{HNF{D}, BigInt}} — per-HNF count (one entry per symmetry-inequivalent HNF in the request). Useful for diagnosing which HNFs dominate the count.

enumerate_hnfs(...) already returns one HNF per symmetry class, so the flat per-HNF list serves the same role a dedicated HNFClass type would. No quotient wrapper is needed today.

EmptyEnumerationError(reason::Symbol, diagnostic::String)

Thrown when the user's request cannot produce any valid structures. reason codes:

• :concentration_unrealizable — fractions don't divide cleanly into n_total (e.g., Concentration([1//5, 4//5]) at VolumeRange(2:4) — no n in 2..4 is divisible by 5).
• :no_active_sites — the user's Sites has only inactive sites (single allowed label per site), so the labeling space is empty.
• :site_restriction_conflict — site restrictions over-constrain the requested concentration.

We throw rather than silently returning an empty result — the caller is more often confused than not when no structures appear.

PartitionExplosionError(partition_count::Int, threshold::Int, diagnostic::String = "")

Thrown when a ConcentrationRange decomposes into too many distinct multiplicity vectors at the requested cell size. Default threshold: 100. Above that, the naïve caller almost certainly wanted a narrower range.

The gate is paternalistic by default; expert users can pass on_partition_overflow = :ignore (or set partition_threshold higher) for literature-validation runs that genuinely want every partition.