diff options
Diffstat (limited to 'morphology/meta_affine/sequence.rs')
| -rw-r--r-- | morphology/meta_affine/sequence.rs | 411 |
1 files changed, 0 insertions, 411 deletions
diff --git a/morphology/meta_affine/sequence.rs b/morphology/meta_affine/sequence.rs deleted file mode 100644 index 784567d..0000000 --- a/morphology/meta_affine/sequence.rs +++ /dev/null @@ -1,411 +0,0 @@ -//! Valid Sequence Generation and Constraint Validation -//! -//! This module implements sequences of meta-affine values subject to four constraints. -//! -//! A valid sequence must satisfy: -//! 1. Every value in the generating set appears at least once -//! 2. No value appears next to itself -//! 3. The last value is (0,0) -//! 4. For each outer value n, the last occurrence of any value (n,m) must have m=0 - -use crate::value::Value; -use crate::set::ValidSet; -use std::collections::{HashMap, HashSet}; - -/// Represents an ordered sequence of meta-affine values. -/// -/// A sequence is valid if it satisfies all four constraints with respect -/// to its generating set. -#[derive(Debug, Clone, PartialEq, Eq)] -pub struct Sequence { - values: Vec<Value>, -} - -impl Sequence { - /// Creates a new sequence from a vector of values. - /// - /// # Examples - /// - /// ``` - /// use meta_affine::{Sequence, Value}; - /// - /// let seq = Sequence::new(vec![Value::new(0,0), Value::new(1,0), Value::new(0,0)]); - /// assert_eq!(seq.length(), 3); - /// ``` - pub fn new(values: Vec<Value>) -> Self { - Sequence { values } - } - - /// Returns the length of the sequence. - pub fn length(&self) -> usize { - self.values.len() - } - - /// Returns a slice of the values in the sequence. - pub fn values(&self) -> &[Value] { - &self.values - } - - /// Checks if the sequence is valid for the given set. - /// - /// # Examples - /// - /// ``` - /// use meta_affine::{Sequence, ValidSet, Value}; - /// - /// let set = ValidSet::origin_set(); - /// let seq = Sequence::new(vec![Value::origin()]); - /// assert!(seq.is_valid(&set)); - /// ``` - pub fn is_valid(&self, set: &ValidSet) -> bool { - check_coverage(self, set) - && check_no_consecutive_duplicates(self) - && check_terminal(self) - && check_outer_value_constraint(self) - } -} - -// ============================================================================ -// CONSTRAINT VALIDATORS -// ============================================================================ - -/// Checks constraint 1: -/// Every value in the set must appear at least once in the sequence. -/// -/// # Examples -/// -/// ``` -/// use meta_affine::{Sequence, ValidSet, Value}; -/// use meta_affine::sequence::check_coverage; -/// -/// let set = ValidSet::origin_set(); -/// let seq = Sequence::new(vec![Value::origin()]); -/// assert!(check_coverage(&seq, &set)); -/// ``` -pub fn check_coverage(sequence: &Sequence, set: &ValidSet) -> bool { - let seq_values: HashSet<Value> = sequence.values.iter().copied().collect(); - - for &value in set.values() { - if !seq_values.contains(&value) { - return false; - } - } - true -} - -/// Checks constraint 2: -/// No value may appear next to itself in the sequence. -/// -/// # Examples -/// -/// ``` -/// use meta_affine::{Sequence, Value}; -/// use meta_affine::sequence::check_no_consecutive_duplicates; -/// -/// let seq1 = Sequence::new(vec![Value::new(0,0), Value::new(1,0), Value::new(0,0)]); -/// assert!(check_no_consecutive_duplicates(&seq1)); -/// -/// let seq2 = Sequence::new(vec![Value::new(0,0), Value::new(0,0)]); -/// assert!(!check_no_consecutive_duplicates(&seq2)); -/// ``` -pub fn check_no_consecutive_duplicates(sequence: &Sequence) -> bool { - for window in sequence.values.windows(2) { - if window[0] == window[1] { - return false; - } - } - true -} - -/// Checks constraint 3: -/// The last value in the sequence must be (0,0). -/// -/// # Examples -/// -/// ``` -/// use meta_affine::{Sequence, Value}; -/// use meta_affine::sequence::check_terminal; -/// -/// let seq1 = Sequence::new(vec![Value::new(1,0), Value::origin()]); -/// assert!(check_terminal(&seq1)); -/// -/// let seq2 = Sequence::new(vec![Value::new(1,0)]); -/// assert!(!check_terminal(&seq2)); -/// ``` -pub fn check_terminal(sequence: &Sequence) -> bool { - if sequence.values.is_empty() { - return false; - } - sequence.values.last() == Some(&Value::origin()) -} - -/// Checks constraint 4: -/// For each outer value n that appears in the sequence, the last occurrence -/// of any value with outer coordinate n must have inner coordinate 0. -/// -/// # Examples -/// -/// ``` -/// use meta_affine::{Sequence, Value}; -/// use meta_affine::sequence::check_outer_value_constraint; -/// -/// // Last occurrence of outer=1 is (1,0) ✓ -/// let seq1 = Sequence::new(vec![Value::new(1,1), Value::new(1,0), Value::new(0,0)]); -/// assert!(check_outer_value_constraint(&seq1)); -/// -/// // Last occurrence of outer=1 is (1,1) ✗ -/// let seq2 = Sequence::new(vec![Value::new(1,0), Value::new(1,1), Value::new(0,0)]); -/// assert!(!check_outer_value_constraint(&seq2)); -/// ``` -pub fn check_outer_value_constraint(sequence: &Sequence) -> bool { - // Map each outer value to the index of its last occurrence - let mut last_index_by_outer: HashMap<i32, usize> = HashMap::new(); - - for (i, &value) in sequence.values.iter().enumerate() { - last_index_by_outer.insert(value.outer, i); - } - - // Check that at each last occurrence, the inner value is 0 - for (_outer, &last_idx) in &last_index_by_outer { - let value_at_last = sequence.values[last_idx]; - if value_at_last.inner != 0 { - return false; - } - } - - true -} - -/// Generates all valid sequences of a given length from a valid set. -/// -/// Uses constrained backtracking with early pruning based on the four constraints. -/// -/// # Arguments -/// -/// * `set` - The valid set to generate sequences from -/// * `length` - The desired sequence length -/// -/// # Returns -/// -/// A vector of all valid sequences of the specified length -/// -/// # Examples -/// -/// ``` -/// use meta_affine::{ValidSet, Value}; -/// use meta_affine::sequence::generate_sequences; -/// -/// let set = ValidSet::origin_set(); -/// let sequences = generate_sequences(&set, 1); -/// assert_eq!(sequences.len(), 1); // Only [(0,0)] -/// ``` -pub fn generate_sequences(set: &ValidSet, length: usize) -> Vec<Sequence> { - // Cannot generate valid sequences if length is 0 or set is empty - if length == 0 || set.size() == 0 { - return Vec::new(); - } - - // Must contain origin for constraint 3 - if !set.contains(&Value::origin()) { - return Vec::new(); - } - - let mut result = Vec::new(); - let set_values: Vec<Value> = set.values().copied().collect(); - - // Start backtracking - let mut current = Vec::new(); - let mut coverage = HashSet::new(); - - backtrack( - &mut current, - &mut coverage, - &set_values, - set, - length, - &mut result, - ); - - result -} - -/// Recursive backtracking function for sequence generation. -fn backtrack( - current: &mut Vec<Value>, - coverage: &mut HashSet<Value>, - set_values: &[Value], - set: &ValidSet, - target_length: usize, - result: &mut Vec<Sequence>, -) { - // Base case: reached target length - if current.len() == target_length { - // Check all constraints - let seq = Sequence::new(current.clone()); - - if check_coverage(&seq, set) - && check_terminal(&seq) - && check_outer_value_constraint(&seq) - { - result.push(seq); - } - return; - } - - // Determine valid next values - let position = current.len(); - let last_value = current.last().copied(); // Copy the value to avoid borrow issues - - // If at last position, must be (0,0) (constraint 3) - if position == target_length - 1 { - let next = Value::origin(); - - // Check constraint 2: no consecutive duplicates - if let Some(last) = last_value { - if last == next { - return; // Cannot place origin here - } - } - - // Check constraint 4 pruning: can we still satisfy it? - current.push(next); - coverage.insert(next); - - if is_outer_constraint_satisfiable(current) { - backtrack(current, coverage, set_values, set, target_length, result); - } - - current.pop(); - if !current.contains(&next) { - coverage.remove(&next); - } - return; - } - - // Try each value from the set - for &next in set_values { - // Constraint 2: cannot repeat last value - if let Some(last) = last_value { - if last == next { - continue; - } - } - - // Add to current path - let was_in_coverage = coverage.contains(&next); - current.push(next); - coverage.insert(next); - - // Pruning: check if we can still satisfy constraints - if can_still_satisfy_constraints(current, coverage, set, target_length) { - backtrack(current, coverage, set_values, set, target_length, result); - } - - // Backtrack - current.pop(); - if !was_in_coverage { - coverage.remove(&next); - } - } -} - -/// Checks if constraints can still be satisfied from current state. -fn can_still_satisfy_constraints( - current: &[Value], - coverage: &HashSet<Value>, - set: &ValidSet, - target_length: usize, -) -> bool { - let remaining_positions = target_length - current.len(); - - // Check constraint 1: Can we still cover all values? - let uncovered = set.size() - coverage.len(); - if uncovered > remaining_positions { - return false; // Not enough space to cover all values - } - - // Check constraint 4: Outer value constraint - // If we've placed a value (n,m) with m≠0, we must be able to place (n,0) later - if !is_outer_constraint_satisfiable(current) { - return false; - } - - true -} - -/// Checks if the outer value constraint can still be satisfied. -/// -/// For any outer value n where we've placed (n,m) with m≠0, -/// we need to ensure (n,0) can still be placed later. -fn is_outer_constraint_satisfiable(current: &[Value]) -> bool { - // Track the last index of each outer value - let mut last_index_by_outer: HashMap<i32, usize> = HashMap::new(); - - for (i, &value) in current.iter().enumerate() { - last_index_by_outer.insert(value.outer, i); - } - - // Check each outer value - for (&outer, &last_idx) in &last_index_by_outer { - let value_at_last = current[last_idx]; - - // If the last occurrence has inner≠0, it's a potential violation - // This is fine if we're still building the sequence, but we should check - // if there's any value after it with the same outer coordinate - let has_later_occurrence = current.iter() - .skip(last_idx + 1) - .any(|v| v.outer == outer); - - if !has_later_occurrence && value_at_last.inner != 0 { - // This is currently the last occurrence and inner≠0 - // This is only ok if this is not the final sequence - // For pruning purposes during generation, we allow it - continue; - } - } - - true -} - -/// Generates all valid sequences of a given length from any valid set. -/// -/// This is the main entry point that combines set generation and sequence generation. -/// -/// # Arguments -/// -/// * `length` - The desired sequence length -/// -/// # Returns -/// -/// A vector of all valid sequences of the specified length -/// -/// # Examples -/// -/// ``` -/// use meta_affine::sequence::generate_all_sequences; -/// -/// let sequences = generate_all_sequences(1); -/// assert_eq!(sequences.len(), 1); // Only [(0,0)] -/// ``` -pub fn generate_all_sequences(length: usize) -> Vec<Sequence> { - use crate::set::generate_valid_sets; - - let max_set_size = length; // Heuristic: set size can't exceed sequence length - let all_sets = generate_valid_sets(max_set_size); - - let mut all_sequences = Vec::new(); - - for set in all_sets { - let sequences = generate_sequences(&set, length); - all_sequences.extend(sequences); - } - - all_sequences -} - -/// Counts the number of valid sequences for a given length without generating them. -/// -/// This is more memory-efficient than generating all sequences when you only need the count. -pub fn count_sequences(set: &ValidSet, length: usize) -> usize { - generate_sequences(set, length).len() -} |