"""Exact finite problem functions on arbitrary competence families.
The algorithms evaluate the defining subset relation, not fringe theorems:
p(C) = {q: there exists A in mu(q) with A <= C}. They support the family
mapping operations of CbKST 0.1-1 and MATLAB KST-toolbox ``skillmap`` while
keeping row identities and exact images separate from structure axioms.
"""
from __future__ import annotations
from collections.abc import Collection
from dataclasses import dataclass
from itertools import combinations
import numpy as np
from numpy.typing import NDArray
from knowledgespaces.derivation.skill_map import SkillMap, SkillMultiMap
from knowledgespaces.structures.knowledge_structure import KnowledgeStructure
from knowledgespaces.structures.set_family import SetFamily
StateRows = Collection[Collection[str]] | KnowledgeStructure | SetFamily
[docs]
@dataclass(frozen=True)
class InverseCompetenceRow:
"""Exact preimages or positive-covering rows for one requested performance.
``minimal_states`` contains distinct inclusion-minimal states among these
rows, in first occurrence order. It is not a smallest-cardinality filter.
Empty tuples denote infeasibility, unlike a tuple containing the empty set.
"""
performance_id: str
performance: frozenset[str]
row_indices: tuple[int, ...]
competence_ids: tuple[str, ...]
competence_states: tuple[frozenset[str], ...]
minimal_states: tuple[frozenset[str], ...]
[docs]
@dataclass(frozen=True)
class CompetenceInverseReport:
"""Inverse results with an explicit exact/positive-coverage interpretation.
Families aggregate the rows without adding endpoints. Neither family
automatically satisfies the axioms of a competence structure.
"""
skills: tuple[str, ...]
items: tuple[str, ...]
exact: bool
rows: tuple[InverseCompetenceRow, ...]
@property
def compatible_family(self) -> SetFamily:
"""Union of all compatible competence states across requested rows."""
return SetFamily(self.skills, [s for r in self.rows for s in r.competence_states])
@property
def minimal_family(self) -> SetFamily:
"""Union of each row's minima, not minima of the aggregate union."""
return SetFamily(self.skills, [s for r in self.rows for s in r.minimal_states])
[docs]
@dataclass(frozen=True, init=False)
class ProblemFunction:
"""A skill map or multimap evaluated on explicit competence rows.
Parameters
----------
skill_map
Item labels and their order are retained, including numeric IDs
represented as strings. Alternatives are OR; skills within each
alternative are AND.
competence_states
Sequence of skill subsets, ``SetFamily``, or ``KnowledgeStructure``.
A sequence retains its order and duplicates. Unordered families use
cardinality then lexicographic order. None enumerates the powerset
in cardinality then ``skills`` order, subject to ``max_states``.
An empty sequence is an empty family, distinct from None.
skills
Optional column order containing each declared skill exactly once;
defaults to sorted skill labels. Skill and item labels may overlap:
they always belong to separate column blocks in ``to_matrix``.
competence_ids
Unique string IDs for the competence rows; defaults to C1, C2, ... .
max_states
Positive integer guard on the number of competence rows. It raises
rather than silently truncating the family. Explicit enumeration
can be exponential in the number of skills.
Notes
-----
The exact image is a ``SetFamily``: p(empty) can be nonempty, and an
arbitrary supplied family can omit either endpoint. Use
``image.to_knowledge_structure()`` to check the structure axioms before
using methods requiring a knowledge structure. This class makes no
claim about effective/collective fringes for general multimaps.
"""
skills: tuple[str, ...]
items: tuple[str, ...]
competence_states: tuple[frozenset[str], ...]
competence_ids: tuple[str, ...]
performance_states: tuple[frozenset[str], ...]
def __init__(
self,
skill_map: SkillMap | SkillMultiMap,
competence_states: StateRows | None = None,
*,
skills: Collection[str] | None = None,
competence_ids: Collection[str] | None = None,
max_states: int = 100_000,
) -> None:
if not isinstance(skill_map, (SkillMap, SkillMultiMap)):
raise TypeError("skill_map must be a SkillMap or SkillMultiMap.")
ordered_skills = tuple(sorted(skill_map.skills) if skills is None else skills)
if (
len(set(ordered_skills)) != len(ordered_skills)
or set(ordered_skills) != skill_map.skills
):
raise ValueError("skills must contain every declared skill exactly once.")
rows = _rows(competence_states, ordered_skills, max_states)
ids = _ids(competence_ids, len(rows), "C")
object.__setattr__(self, "skills", ordered_skills)
object.__setattr__(self, "items", skill_map.items)
object.__setattr__(self, "competence_states", rows)
object.__setattr__(self, "competence_ids", ids)
object.__setattr__(
self, "performance_states", tuple(skill_map.problem_function(s) for s in rows)
)
@property
def competence_family(self) -> SetFamily:
"""Distinct supplied competence states, without adding endpoints."""
return SetFamily(self.skills, self.competence_states)
@property
def image(self) -> SetFamily:
"""Exact set image p(C), dropping duplicate images but adding nothing."""
return SetFamily(self.items, self.performance_states)
@property
def equivalence_classes(self) -> tuple[PerformanceClass, ...]:
"""Partition competence rows by their identical performance images."""
groups: dict[frozenset[str], list[int]] = {}
for i, performance in enumerate(self.performance_states):
groups.setdefault(performance, []).append(i)
return tuple(
PerformanceClass(
performance,
tuple(indices),
tuple(self.competence_ids[i] for i in indices),
tuple(self.competence_states[i] for i in indices),
)
for performance, indices in groups.items()
)
[docs]
def to_matrix(self) -> NDArray[np.int8]:
"""Binary table: skill columns followed by item columns, one row per ID.
Labels/order are ``skills + items``; the two blocks are distinct even
if a skill and an item share a label. Returns an independent array of
shape (number of competence rows, number of skills + number of items).
Slice at ``len(skills)`` for the row-preserving performance matrix.
"""
return np.asarray(
[
[int(s in c) for s in self.skills] + [int(q in p) for q in self.items]
for c, p in zip(self.competence_states, self.performance_states, strict=True)
],
dtype=np.int8,
).reshape(len(self.competence_states), len(self.skills) + len(self.items))
[docs]
def inverse(
self,
performance_states: StateRows | None = None,
*,
performance_ids: Collection[str] | None = None,
exact: bool = True,
max_states: int = 100_000,
) -> CompetenceInverseReport:
"""Report compatible rows and their minima for each requested performance.
``exact=True`` means p(C) = K, including the absence of other items.
``exact=False`` means K <= p(C): only positive mastery is required,
as in CbKST ``cbkst_perf2comp``. Requested order, duplicates and IDs
are retained; unattainable rows remain visible with empty results.
None enumerates all item subsets, guarded by ``max_states``. Results
always refer to this problem function's supplied competence rows,
so minima are taken within the admissible family, not unrestricted
competencies subsequently filtered for admissibility.
"""
if not isinstance(exact, bool):
raise ValueError("exact must be a bool.")
performances = _rows(performance_states, self.items, max_states)
ids = _ids(performance_ids, len(performances), "P")
result = []
for performance, row_id in zip(performances, ids, strict=True):
indices = tuple(
i
for i, p in enumerate(self.performance_states)
if (p == performance if exact else performance <= p)
)
states = tuple(self.competence_states[i] for i in indices)
unique = tuple(dict.fromkeys(states))
minimal = tuple(s for s in unique if not any(t < s for t in unique))
result.append(
InverseCompetenceRow(
row_id,
performance,
indices,
tuple(self.competence_ids[i] for i in indices),
states,
minimal,
)
)
return CompetenceInverseReport(self.skills, self.items, exact, tuple(result))
def _rows(
states: StateRows | None, domain: tuple[str, ...], max_states: int
) -> tuple[frozenset[str], ...]:
if isinstance(max_states, bool) or not isinstance(max_states, int) or max_states < 1:
raise ValueError("max_states must be a positive integer.")
if states is None:
if 2 ** len(domain) > max_states:
raise ValueError(
"Powerset exceeds max_states; supply an explicit family or raise the limit."
)
return tuple(frozenset(s) for n in range(len(domain) + 1) for s in combinations(domain, n))
if isinstance(states, (KnowledgeStructure, SetFamily)) and states.domain != frozenset(domain):
raise ValueError("Supplied family and mapping must have the same domain.")
if len(states) > max_states:
raise ValueError("Supplied family exceeds max_states.")
if isinstance(states, (KnowledgeStructure, SetFamily, set, frozenset)):
rows = tuple(sorted((frozenset(s) for s in states), key=lambda s: (len(s), sorted(s))))
else:
rows = tuple(frozenset(s) for s in states)
if any(not s <= frozenset(domain) for s in rows):
raise ValueError("A supplied state contains labels outside the domain.")
return rows
def _ids(ids: Collection[str] | None, n: int, prefix: str) -> tuple[str, ...]:
if ids is None:
return tuple(f"{prefix}{i + 1}" for i in range(n))
result = tuple(ids)
if len(result) != n or any(not isinstance(i, str) for i in result) or len(set(result)) != n:
raise ValueError("Row IDs must be unique strings, one per supplied row.")
return result