Source code for knowledgespaces.derivation.inverse

"""Inverse problem-function computations for conjunctive maps and multimaps.

These are finite set computations using p(C) = {q: some A in mu(q) is a
subset of C}. No fringe or floor theorem for conjunctive models is extended
to multimaps. See Falmagne & Doignon (2011), Chapter 6, and the distinction
between exact inversion and positive-item coverage in the user guide.
"""

from __future__ import annotations

from collections.abc import Collection

from knowledgespaces.derivation.skill_map import SkillMap, SkillMultiMap
from knowledgespaces.structures.knowledge_structure import KnowledgeStructure
from knowledgespaces.structures.set_family import SetFamily




def compatible_competencies(
    performance: Collection[str],
    skill_map: SkillMap | SkillMultiMap,
    competence_structure: KnowledgeStructure | SetFamily,
    *,
    exact: bool = True,
) -> frozenset[frozenset[str]]:
    """Return admissible C with p(C) = performance (default).

    With ``exact=False``, return C with ``performance <= p(C)``: only the
    specified mastered items constrain the result. The domain of the supplied
    competence structure or set family must equal the skill domain. A
    ``SetFamily`` need not contain either endpoint. An unattainable exact
    performance yields the empty family, not an invented competence state.
    """
    target = _validate(performance, skill_map, exact)
    if competence_structure.domain != skill_map.skills:
        raise ValueError("Competence structure and skill map must have the same skill domain.")
    return frozenset(
        c
        for c in competence_structure
        if (
            skill_map.problem_function(c) == target
            if exact
            else target <= skill_map.problem_function(c)
        )
    )





def minimal_competencies(
    performance: Collection[str],
    skill_map: SkillMap | SkillMultiMap,
    *,
    competence_structure: KnowledgeStructure | SetFamily | None = None,
    exact: bool = True,
    max_candidates: int = 100_000,
) -> frozenset[frozenset[str]]:
    """All inclusion-minimal compatible competence states.

    By default compatibility means exact performance, including the absence
    of mastery of every other item. ``exact=False`` asks instead for minimal
    skill sets sufficient to solve the specified items, as in the positive
    coverage interpretation of ``CbKST::cbkst_perf2comp``.

    If a competence structure or set family is given, minimize within its admissible states;
    a minimal unrestricted solution may not itself be admissible. Otherwise
    every subset of the skill domain is admissible. The unrestricted algorithm
    builds minimal unions of alternative competencies incrementally, without
    enumerating the entire skill powerset. Its intermediate antichains can
    nevertheless be exponential. ``max_candidates`` bounds each intermediate
    family (before minimization), raising rather than returning partial output.

    Minimal means set inclusion, not smallest cardinality. The empty family
    means infeasibility; ``frozenset({frozenset()})`` is a valid empty-skill
    solution. No probability or inference about noisy responses is involved.
    """
    target = _validate(performance, skill_map, exact)
    if (
        isinstance(max_candidates, bool)
        or not isinstance(max_candidates, int)
        or max_candidates < 1
    ):
        raise ValueError("max_candidates must be a positive integer.")
    if competence_structure is not None:
        candidates = compatible_competencies(target, skill_map, competence_structure, exact=exact)
        if len(candidates) > max_candidates:
            raise ValueError("Compatible family exceeds max_candidates.")
        return _minimal(candidates)

    multi = (
        SkillMultiMap.from_skill_map(skill_map) if isinstance(skill_map, SkillMap) else skill_map
    )
    candidates = frozenset({frozenset()})
    for item in sorted(target):
        combined: set[frozenset[str]] = set()
        for state in candidates:
            for alternative in multi.competencies_for(item):
                union = state | alternative
                # p is isotone: a forbidden mastered item cannot disappear
                # after adding more skills, so this pruning is exact.
                if exact and not multi.problem_function(union) <= target:
                    continue
                combined.add(union)
                if len(combined) > max_candidates:
                    raise ValueError("Intermediate competence family exceeds max_candidates.")
        candidates = _minimal(combined)
    # Also handles the empty target and items with empty competencies.
    return frozenset(c for c in candidates if not exact or multi.problem_function(c) == target)



def _validate(
    performance: Collection[str], skill_map: SkillMap | SkillMultiMap, exact: bool
) -> frozenset[str]:
    if not isinstance(exact, bool):
        raise ValueError("exact must be a bool.")
    target = frozenset(performance)
    if not target <= set(skill_map.items):
        raise ValueError("Performance contains unknown items.")
    return target


def _minimal(states: Collection[frozenset[str]]) -> frozenset[frozenset[str]]:
    result: set[frozenset[str]] = set()
    for state in sorted(states, key=lambda s: (len(s), sorted(s))):
        if not any(smaller <= state for smaller in result):
            result.add(state)
    return frozenset(result)