Struct ExactCoverBy3Sets 

pub struct ExactCoverBy3Sets { /* private fields */ }

Exact Cover by 3-Sets (X3C) problem.

Given a universe X = {0, 1, …, 3q-1} and a collection C of 3-element subsets of X, determine if there exists a subcollection C’ of exactly q subsets such that every element of X appears in exactly one member of C’.

This is a classical NP-complete problem (Karp, 1972), widely used as a source problem for NP-completeness reductions.

Example

use problemreductions::models::set::ExactCoverBy3Sets;
use problemreductions::{Problem, Solver, BruteForce};

// Universe: {0, 1, 2, 3, 4, 5} (q = 2)
// Subsets: S0={0,1,2}, S1={3,4,5}, S2={0,3,4}
let problem = ExactCoverBy3Sets::new(
    6,
    vec![[0, 1, 2], [3, 4, 5], [0, 3, 4]],
);

let solver = BruteForce::new();
let solutions = solver.find_all_satisfying(&problem);

// S0 and S1 form an exact cover
assert_eq!(solutions.len(), 1);
assert!(problem.evaluate(&solutions[0]));

Implementations

impl ExactCoverBy3Sets

pub fn new(universe_size: usize, subsets: Vec<[usize; 3]>) -> Self

Create a new X3C problem.

Panics

Panics if universe_size is not divisible by 3, or if any subset contains duplicate elements or elements outside the universe.

pub fn universe_size(&self) -> usize

Get the universe size.

pub fn num_subsets(&self) -> usize

Get the number of subsets in the collection.

pub fn subsets(&self) -> &[[usize; 3]]

Get the subsets.

pub fn get_subset(&self, index: usize) -> Option<&[usize; 3]>

Get a specific subset.

pub fn is_valid_solution(&self, config: &[usize]) -> bool

Check if a configuration is a valid exact cover.

A valid exact cover selects exactly q = universe_size/3 subsets that are pairwise disjoint and whose union equals the universe.

pub fn covered_elements(&self, config: &[usize]) -> HashSet<usize>

Get the elements covered by the selected subsets.

Trait Implementations

impl Clone for ExactCoverBy3Sets

fn clone(&self) -> ExactCoverBy3Sets

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for ExactCoverBy3Sets

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for ExactCoverBy3Sets

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for ExactCoverBy3Sets

const NAME: &'static str = "ExactCoverBy3Sets"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Metric = bool

The evaluation metric type.

fn dims(&self) -> Vec<usize>

Configuration space dimensions. Each entry is the cardinality of that variable.

fn evaluate(&self, config: &[usize]) -> bool

Evaluate the problem on a configuration.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl Serialize for ExactCoverBy3Sets

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl DeclaredVariant for ExactCoverBy3Sets

impl SatisfactionProblem for ExactCoverBy3Sets