problemreductions/models/algebraic/

consecutive_ones_submatrix.rs

//! Consecutive Ones Submatrix problem implementation.
//!
//! Given an m×n binary matrix A and an integer 0 ≤ K ≤ n, determine whether
//! there exists a subset of K columns whose columns can be permuted so that in
//! each row all 1's occur consecutively. The implementation treats K = 0 as the
//! vacuous empty-submatrix case. NP-complete (Booth, 1975) via
//! transformation from Hamiltonian Path.

use crate::registry::{FieldInfo, ProblemSchemaEntry};
use crate::traits::Problem;
use serde::{Deserialize, Serialize};

inventory::submit! {
    ProblemSchemaEntry {
        name: "ConsecutiveOnesSubmatrix",
        display_name: "Consecutive Ones Submatrix",
        aliases: &[],
        dimensions: &[],
        category: crate::registry::ProblemCategory::Algebraic,
        module_path: module_path!(),
        description: "Find K columns of a binary matrix that can be permuted to have the consecutive ones property",
        fields: &[
            FieldInfo { name: "matrix", type_name: "Vec<Vec<bool>>", description: "m×n binary matrix A" },
            FieldInfo { name: "bound", type_name: "i64", description: "Required number of columns K" },
        ],
    }
}

/// The Consecutive Ones Submatrix problem.
///
/// Given an m×n binary matrix A and an integer 0 ≤ K ≤ n, determine
/// whether there exists a subset of K columns that has the "consecutive ones
/// property" — i.e., the columns can be permuted so that in each row all 1's
/// occur consecutively. The implementation treats K = 0 as vacuously
/// satisfiable.
///
/// # Representation
///
/// Each column has a binary variable: `x_j = 1` if column j is selected.
/// The problem is satisfiable iff exactly K columns are selected and some
/// permutation of those columns gives each row consecutive 1's. The current
/// evaluator checks those permutations explicitly with Heap's algorithm.
///
/// # Example
///
/// ```
/// use problemreductions::models::algebraic::ConsecutiveOnesSubmatrix;
/// use problemreductions::{Problem, BruteForce};
///
/// // Tucker matrix (3×4) — full matrix does NOT have C1P, but K=3 does.
/// let matrix = vec![
///     vec![true, true, false, true],
///     vec![true, false, true, true],
///     vec![false, true, true, false],
/// ];
/// let problem = ConsecutiveOnesSubmatrix::new(matrix, 3);
/// let solver = BruteForce::new();
/// let solution = solver.solve(&problem).unwrap();
/// assert!(solution.is_some());
/// ```
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(try_from = "ConsecutiveOnesSubmatrixData")]
pub struct ConsecutiveOnesSubmatrix {
    matrix: Vec<Vec<bool>>,
    bound: i64,
}

#[derive(Deserialize)]
struct ConsecutiveOnesSubmatrixData {
    matrix: Vec<Vec<bool>>,
    bound: i64,
}

impl TryFrom<ConsecutiveOnesSubmatrixData> for ConsecutiveOnesSubmatrix {
    type Error = crate::registry::ConstructionError;

    fn try_from(data: ConsecutiveOnesSubmatrixData) -> Result<Self, Self::Error> {
        Self::try_new(data.matrix, data.bound)
    }
}

impl ConsecutiveOnesSubmatrix {
    /// Create a new ConsecutiveOnesSubmatrix instance.
    ///
    /// # Panics
    ///
    /// Panics if `bound > n`, or if rows have inconsistent lengths.
    pub fn new(matrix: Vec<Vec<bool>>, bound: i64) -> Self {
        Self::try_new(matrix, bound).unwrap_or_else(|error| panic!("{error}"))
    }

    fn try_new(
        matrix: Vec<Vec<bool>>,
        bound: i64,
    ) -> Result<Self, crate::registry::ConstructionError> {
        let n = matrix.first().map_or(0, Vec::len);
        if matrix.iter().any(|row| row.len() != n) {
            return Err("all matrix rows must have the same length".into());
        }
        if !(bound < 0 || usize::try_from(bound).is_ok_and(|bound| bound <= n)) {
            return Err(format!("bound ({bound}) must be <= number of columns ({n})").into());
        }
        Ok(Self { matrix, bound })
    }

    /// Returns the binary matrix.
    pub fn matrix(&self) -> &[Vec<bool>] {
        &self.matrix
    }

    /// Returns the bound (the required number of columns).
    pub fn bound(&self) -> i64 {
        self.bound
    }

    /// Returns the number of rows (m).
    pub fn num_rows(&self) -> usize {
        self.matrix.len()
    }

    /// Returns the number of columns (n).
    pub fn num_cols(&self) -> usize {
        if self.matrix.is_empty() {
            0
        } else {
            self.matrix[0].len()
        }
    }

    /// Check if a given column ordering has the consecutive ones property.
    ///
    /// `col_order` is a permutation of K column indices.
    fn has_c1p(&self, col_order: &[usize]) -> bool {
        for row in &self.matrix {
            let mut first_one = None;
            let mut last_one = None;
            let mut count_ones = 0;
            for (pos, &col_idx) in col_order.iter().enumerate() {
                if row[col_idx] {
                    if first_one.is_none() {
                        first_one = Some(pos);
                    }
                    last_one = Some(pos);
                    count_ones += 1;
                }
            }
            // Ones are consecutive iff (last - first + 1) == count
            if count_ones > 0 {
                let span = last_one.unwrap() - first_one.unwrap() + 1;
                if span != count_ones {
                    return false;
                }
            }
        }
        true
    }

    /// Check if any permutation of the given columns has C1P.
    fn any_permutation_has_c1p(&self, cols: &[usize]) -> bool {
        let k = cols.len();
        if k == 0 {
            return true;
        }
        let mut perm: Vec<usize> = cols.to_vec();
        // Generate all permutations using Heap's algorithm
        let mut c = vec![0usize; k];
        if self.has_c1p(&perm) {
            return true;
        }
        let mut i = 0;
        while i < k {
            if c[i] < i {
                if i % 2 == 0 {
                    perm.swap(0, i);
                } else {
                    perm.swap(c[i], i);
                }
                if self.has_c1p(&perm) {
                    return true;
                }
                c[i] += 1;
                i = 0;
            } else {
                c[i] = 0;
                i += 1;
            }
        }
        false
    }
}

impl Problem for ConsecutiveOnesSubmatrix {
    const NAME: &'static str = "ConsecutiveOnesSubmatrix";
    type Solution = Vec<bool>;
    type Value = crate::types::Or;

    crate::problem_parameters![
        ("bound", bound),
        ("num_cols", num_cols),
        ("num_rows", num_rows),
    ];

    fn variant() -> Vec<(&'static str, &'static str)> {
        crate::variant_params![]
    }

    fn evaluate(
        &self,
        config: &Self::Solution,
    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
        Ok({
            crate::types::Or({
                if config.len() != self.num_cols() {
                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
                        "column-selection length does not match the matrix".into(),
                    ));
                }
                // Collect selected column indices
                let selected: Vec<usize> = config
                    .iter()
                    .enumerate()
                    .filter(|(_, &v)| v)
                    .map(|(i, _)| i)
                    .collect();
                if usize::try_from(self.bound) != Ok(selected.len()) {
                    return Ok(crate::types::Or(false));
                }
                self.any_permutation_has_c1p(&selected)
            })
        })
    }
}

impl crate::solvers::BruteForceProblem for ConsecutiveOnesSubmatrix {
    fn dimensions(&self) -> Vec<usize> {
        vec![2; self.num_cols()]
    }
}

crate::declare_variants! {
    default ConsecutiveOnesSubmatrix => "2^(num_cols) * (num_rows + num_cols)",
}

crate::register_brute_force! {
    ConsecutiveOnesSubmatrix decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "consecutive_ones_submatrix",
        // Tucker matrix (3×4): full matrix lacks C1P, but K=3 works
        // Select columns {0,1,3} (config [1,1,0,1])
        instance: Box::new(ConsecutiveOnesSubmatrix::new(
            vec![
                vec![true, true, false, true],
                vec![true, false, true, true],
                vec![false, true, true, false],
            ],
            3,
        )),
        optimal_config: serde_json::json!(vec![true, true, false, true]),
        optimal_value: serde_json::json!(true),
    }]
}

#[cfg(test)]
#[path = "../../unit_tests/models/algebraic/consecutive_ones_submatrix.rs"]
mod tests;