Exact Cover API Reference
Data
Data model for ExactCover use case.
ExactCoverData
Bases: UcData
Data for the Exact Cover Problem.
Given a universe of elements and a collection of subsets, the Exact Cover problem asks whether there exists a sub-collection of subsets such that every element is contained in exactly one subset.
Attributes:
| Name | Type | Description |
|---|---|---|
name |
Literal['exact_cover']
|
Identifier for this data type. |
subset_matrix |
NumPyArray
|
A matrix where each row represents a subset and each column an element. subset_matrix[i][j] = 1 if subset i contains element j, 0 otherwise. |
n_elements |
int
|
Number of elements in the universe. |
plot(*, ax: Axes | None = None) -> Axes
Plot the subset matrix as a binary heatmap.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
ax
|
Axes | None
|
Matplotlib axes to draw on. Creates a new figure if |
None
|
Returns:
| Type | Description |
|---|---|
Axes
|
The axes with the plot. |
to_string() -> str
Return a string describing the data.
Returns:
| Type | Description |
|---|---|
str
|
String representation of the data. |
from_matrix(subset_matrix: list[list[int]] | NDArray[np.int_]) -> ExactCoverData
staticmethod
Create an ExactCoverData instance from a subset matrix.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
subset_matrix
|
list[list[int]] | NDArray[int_]
|
A matrix where each row is a subset and each column an element.
|
required |
Returns:
| Type | Description |
|---|---|
ExactCoverData
|
An ExactCoverData instance with the given matrix. |
Examples:
from_subsets(subsets: list[list[int | str]], elements: list[int | str] | None = None) -> ExactCoverData
staticmethod
Create an ExactCoverData instance from element and subset lists.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
subsets
|
list[list[int | str]]
|
List of subsets, where each subset is a list of elements. |
required |
elements
|
list[int | str] | None
|
List of all elements in the universe. If |
None
|
Returns:
| Type | Description |
|---|---|
ExactCoverData
|
An ExactCoverData instance with the generated subset matrix. |
Examples:
generate_random(n_elements: int = 5, n_subsets: int = 8, density: float = 0.4, seed: int | None = None) -> ExactCoverData
staticmethod
Generate a random exact cover instance.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
n_elements
|
int
|
Number of elements in the universe, by default 5. |
5
|
n_subsets
|
int
|
Number of subsets, by default 8. |
8
|
density
|
float
|
Probability that an element is included in a subset, by default 0.4. |
0.4
|
seed
|
int | None
|
Random seed for reproducibility, by default None. |
None
|
Returns:
| Type | Description |
|---|---|
ExactCoverData
|
A randomly generated exact cover instance. |
Formulation
Formulation for ExactCover use case.
ExactCoverFormulation
Bases: UcFormulation[ExactCoverData, ExactCoverSolution]
Constraint-based formulation for the Exact Cover Problem.
Mathematical Formulation
Decision Variables: x_s in {0,1} for each subset s: 1 if subset s is selected
Objective: minimize sum_s x_s (minimize number of subsets used)
Constraints: For each element e: sum_{s containing e} x_s == 1 (each element must be covered exactly once)
to_string(data: ExactCoverData) -> str
staticmethod
Return a string describing the formulation.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
ExactCoverData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
str
|
String representation of the formulation. |
formulate(data: ExactCoverData) -> Model
staticmethod
Formulate the Exact Cover Problem using constraint-based approach.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
ExactCoverData
|
The Exact Cover instance data. |
required |
Returns:
| Type | Description |
|---|---|
Model
|
A Luna Model ready to be solved. |
Raises:
| Type | Description |
|---|---|
EmptyDataError
|
If the subset matrix is empty or has zero size. |
InvalidProblemStructureError
|
If any element is not covered by any subset (infeasible problem). |
interpret(solution: Solution, data: ExactCoverData) -> ExactCoverSolution
staticmethod
Extract solution from quantum result.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
solution
|
Solution
|
The quantum solution. |
required |
data
|
ExactCoverData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
ExactCoverSolution
|
Structured solution with metrics. |
Solution
Solution model for ExactCover use case.
ExactCoverSolution
Bases: UcSolution
Solution for the Exact Cover Problem.
Attributes:
| Name | Type | Description |
|---|---|---|
name |
Literal['exact_cover']
|
Identifier for this solution type. |
selected_subsets |
list[int]
|
Indices of selected subsets forming the exact cover. |
n_subsets_used |
int
|
Number of subsets used in the solution. |
is_valid |
bool
|
Whether each element is covered exactly once. |
plot(data: ExactCoverData | None = None, *, ax: Axes | None = None) -> Axes
Plot the exact cover solution.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
ExactCoverData | None
|
Problem data for context. |
None
|
ax
|
Axes | None
|
Matplotlib axes to draw on. Creates a new figure if |
None
|
Returns:
| Type | Description |
|---|---|
Axes
|
The axes with the plot. |
to_string() -> str
Return a string describing the solution.
Returns:
| Type | Description |
|---|---|
str
|
String representation of the solution. |
Instance
Instance model for ExactCover use case.
ExactCoverInstance
Bases: UcInstance[ExactCoverData, ExactCoverFormulation, ExactCoverSolution]
Instance combining data and formulation for ExactCover.
Collection
Collection of ExactCover instances.
ExactCoverCollection
Bases: UcInstanceCollection[ExactCoverInstance]
Collection of Exact Cover instances.
This collection provides methods to generate benchmark instances with various characteristics for testing and evaluation.
from_random(min_num_elements: int, max_num_elements: int, num_instances: int = 1, *, density: float = 0.4, subset_ratio: float = 1.6, seed: int | None = None) -> ExactCoverCollection
classmethod
Generate random exact cover instances.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
min_num_elements
|
int
|
Minimum number of elements per instance. |
required |
max_num_elements
|
int
|
Maximum number of elements per instance. |
required |
num_instances
|
int
|
Number of instances per size, by default 1. |
1
|
density
|
float
|
Probability that an element is included in a subset, by default 0.4. |
0.4
|
subset_ratio
|
float
|
Ratio of subsets to elements, by default 1.6. |
1.6
|
seed
|
int | None
|
Random seed for reproducibility, by default None. |
None
|
Returns:
| Type | Description |
|---|---|
ExactCoverCollection
|
Collection containing generated instances. |