"""
Skill maps and skill multimaps: mappings from items to skills.
A (conjunctive) skill map μ assigns to each item q the set of skills
μ(q) needed to solve it; the problem function p(C) = {q ∈ Q | μ(q) ⊆ C}
maps a competence state to the set of solvable items. A skill multimap
assigns to each item a nonempty collection of *competencies* —
alternative skill sets, each sufficient on its own — and the problem
function becomes p(C) = {q ∈ Q | some competency of q is ⊆ C}
(conjunctive within a competency, disjunctive across competencies).
The conjunctive skill map is the one-competency special case.
References:
Doignon, J.-P., & Falmagne, J.-C. (1999).
Knowledge Spaces, Chapter 4. Springer-Verlag.
Falmagne, J.-C., & Doignon, J.-P. (2011).
Learning Spaces, Chapter 6. Springer-Verlag.
"""
from __future__ import annotations
from collections.abc import Collection, Mapping
[docs]
class SkillMap:
"""Mapping from items to the skills required to solve them.
Parameters
----------
items : Collection[str]
The domain of items.
skills : Collection[str]
The set of all skills.
mapping : Mapping[str, Collection[str]]
For each item, the skills required to solve it: μ(q).
Raises
------
ValueError
If an item references a skill not in the skills set,
or if mapping keys don't match items.
"""
__slots__ = ("_items", "_mapping", "_skills")
def __init__(
self,
items: Collection[str],
skills: Collection[str],
mapping: Mapping[str, Collection[str]],
) -> None:
self._items: tuple[str, ...] = tuple(items)
self._skills: frozenset[str] = frozenset(skills)
items_set = set(self._items)
if len(items_set) != len(self._items):
raise ValueError("Item labels must be unique.")
extra_keys = set(mapping.keys()) - items_set
if extra_keys:
raise ValueError(f"Mapping contains keys not in items: {extra_keys}")
built: dict[str, frozenset[str]] = {}
for item in self._items:
if item not in mapping:
raise ValueError(f"Item '{item}' has no skill mapping.")
required = frozenset(mapping[item])
extra = required - self._skills
if extra:
raise ValueError(f"Item '{item}' references unknown skills: {set(extra)}")
built[item] = required
self._mapping: dict[str, frozenset[str]] = built
@property
def items(self) -> tuple[str, ...]:
return self._items
@property
def skills(self) -> frozenset[str]:
return self._skills
[docs]
def skills_for(self, item: str) -> frozenset[str]:
"""Return μ(q): skills required by item q."""
return self._mapping[item]
[docs]
def problem_function(self, competence: frozenset[str]) -> frozenset[str]:
"""Compute p(C) = {q ∈ Q | μ(q) ⊆ C}.
An item is solvable iff ALL its required skills are present
in the competence state.
"""
return frozenset(item for item in self._items if self._mapping[item].issubset(competence))
[docs]
def to_matrix(self) -> tuple[list[str], list[str], list[list[int]]]:
"""Return (items, skills, binary matrix).
matrix[i][j] = 1 iff skill skills[j] is required by items[i].
"""
skills_ordered = sorted(self._skills)
skill_idx = {s: j for j, s in enumerate(skills_ordered)}
matrix = []
for item in self._items:
row = [0] * len(skills_ordered)
for s in self._mapping[item]:
row[skill_idx[s]] = 1
matrix.append(row)
return list(self._items), skills_ordered, matrix
[docs]
def atomic_items(self) -> dict[str, frozenset[str]]:
"""Items atomic for each skill (Stefanutti & de Chiusole 2017, Def. 3).
q is atomic for s if s belongs to μ(q) and no strictly smaller
item requirement contains s. Equal requirements remain distinct
items. Cost ``O(|S| |Q|**2)``, without enumerating competence states.
"""
return {
s: frozenset(
q
for q in self._items
if s in self._mapping[q]
and not any(
s in self._mapping[r] and self._mapping[r] < self._mapping[q]
for r in self._items
)
)
for s in sorted(self._skills)
}
@property
def is_exclusive(self) -> bool:
"""No item is atomic for two different skills (2017, Definition 4).
Equivalence with well-gradedness of the floor family requires a
compatible competence space (Proposition 10); this property alone
makes no assertion about an arbitrary competence structure.
"""
seen: set[str] = set()
for items in self.atomic_items().values():
if seen & items:
return False
seen.update(items)
return True
[docs]
@classmethod
def from_matrix(
cls,
items: list[str],
skills: list[str],
matrix: list[list[int]],
) -> SkillMap:
"""Create from a binary matrix.
matrix[i][j] = 1 means items[i] requires skills[j].
Item and skill labels must each be unique. Item order is retained;
skill columns are interpreted in the supplied order.
Raises
------
ValueError
If item or skill labels repeat, matrix dimensions don't match
items/skills, or values are not 0 or 1.
"""
if len(set(skills)) != len(skills):
raise ValueError("Skill labels must be unique.")
if len(matrix) != len(items):
raise ValueError(f"Matrix has {len(matrix)} rows but {len(items)} items.")
for i, row in enumerate(matrix):
if len(row) != len(skills):
raise ValueError(f"Row {i} has {len(row)} columns but {len(skills)} skills.")
for j, val in enumerate(row):
if val not in (0, 1):
raise ValueError(f"Matrix[{i}][{j}] = {val!r}, expected 0 or 1.")
mapping: dict[str, frozenset[str]] = {}
for i, item in enumerate(items):
required = frozenset(skills[j] for j, val in enumerate(matrix[i]) if val)
mapping[item] = required
return cls(items, skills, mapping)
def __repr__(self) -> str:
return f"SkillMap(items={len(self._items)}, skills={len(self._skills)})"
[docs]
class SkillMultiMap:
"""Mapping from items to alternative competencies (skill multimap).
A skill multimap assigns to each item q a nonempty collection μ(q)
of *competencies*: alternative sets of skills, each sufficient on
its own to solve q (Doignon & Falmagne 1999, Chapter 4). The model
is conjunctive within a competency and disjunctive across
competencies; the conjunctive :class:`SkillMap` is the special case
with exactly one competency per item.
The class exposes the same ``items`` / ``skills`` /
``problem_function`` protocol as :class:`SkillMap`, so it plugs
into :func:`knowledgespaces.derivation.derive_knowledge_structure`
unchanged.
Parameters
----------
items : Collection[str]
The domain of items.
skills : Collection[str]
The set of all skills.
mapping : Mapping[str, Collection[Collection[str]]]
For each item, the nonempty collection of its competencies.
Duplicate competencies are dropped; a competency that is a
superset of another is redundant but harmless. An empty
competency means the item is solvable without any skill.
Raises
------
ValueError
If an item is missing from the mapping, has an empty collection
of competencies, or references a skill not in the skills set.
"""
__slots__ = ("_items", "_mapping", "_skills")
def __init__(
self,
items: Collection[str],
skills: Collection[str],
mapping: Mapping[str, Collection[Collection[str]]],
) -> None:
self._items: tuple[str, ...] = tuple(items)
self._skills: frozenset[str] = frozenset(skills)
items_set = set(self._items)
if len(items_set) != len(self._items):
raise ValueError("Item labels must be unique.")
extra_keys = set(mapping.keys()) - items_set
if extra_keys:
raise ValueError(f"Mapping contains keys not in items: {extra_keys}")
built: dict[str, tuple[frozenset[str], ...]] = {}
for item in self._items:
if item not in mapping:
raise ValueError(f"Item '{item}' has no competency mapping.")
competencies = tuple(dict.fromkeys(frozenset(c) for c in mapping[item]))
if not competencies:
raise ValueError(
f"Item '{item}' has no competency; a skill multimap "
f"assigns at least one competency to every item."
)
for comp in competencies:
extra = comp - self._skills
if extra:
raise ValueError(f"Item '{item}' references unknown skills: {set(extra)}")
built[item] = competencies
self._mapping: dict[str, tuple[frozenset[str], ...]] = built
@property
def items(self) -> tuple[str, ...]:
return self._items
@property
def skills(self) -> frozenset[str]:
return self._skills
[docs]
def competencies_for(self, item: str) -> tuple[frozenset[str], ...]:
"""Return μ(q): the alternative competencies of item q."""
return self._mapping[item]
[docs]
def problem_function(self, competence: frozenset[str]) -> frozenset[str]:
"""Compute p(C) = {q ∈ Q | some competency of q is ⊆ C}.
An item is solvable iff AT LEAST ONE of its competencies is
fully contained in the competence state.
"""
return frozenset(
item
for item in self._items
if any(comp.issubset(competence) for comp in self._mapping[item])
)
[docs]
@classmethod
def from_skill_map(cls, skill_map: SkillMap) -> SkillMultiMap:
"""Lift a conjunctive skill map to the one-competency multimap."""
return cls(
skill_map.items,
skill_map.skills,
{item: [skill_map.skills_for(item)] for item in skill_map.items},
)
[docs]
def to_matrix(self) -> tuple[list[str], list[str], list[list[int]]]:
"""Return repeated item labels, sorted skills and binary competency rows.
There is one row per alternative competency, as in CbKST tables.
Unused skills remain columns. Empty competencies are all-zero rows.
"""
skills = sorted(self._skills)
items, matrix = [], []
for item in self._items:
for competency in self._mapping[item]:
items.append(item)
matrix.append([int(s in competency) for s in skills])
return items, skills, matrix
[docs]
@classmethod
def from_matrix(
cls, items: list[str], skills: list[str], matrix: list[list[int]]
) -> SkillMultiMap:
"""Construct from one binary row per competency (items may repeat).
Repeated item rows encode alternatives, not additional conjunctive
requirements. First occurrence determines item order. Skill labels
must be unique; duplicate competencies are deduplicated by the class.
"""
if len(set(skills)) != len(skills):
raise ValueError("Skill labels must be unique.")
if len(items) != len(matrix):
raise ValueError("Each competency row must have an item label.")
mapping: dict[str, list[frozenset[str]]] = {}
for item, row in zip(items, matrix, strict=True):
if len(row) != len(skills) or any(v not in (0, 1) for v in row):
raise ValueError("Expected binary competency rows matching the skill columns.")
mapping.setdefault(item, []).append(
frozenset(s for s, bit in zip(skills, row, strict=True) if bit)
)
return cls(list(mapping), skills, mapping)
def __repr__(self) -> str:
n_comp = sum(len(c) for c in self._mapping.values())
return (
f"SkillMultiMap(items={len(self._items)}, "
f"skills={len(self._skills)}, competencies={n_comp})"
)