feat: basic minimization algorithm

1 files changed, 271 insertions, 1 deletions

diff --git a/src/main.rs b/src/main.rs
index e7a11a9..18d6ca2 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,3 +1,273 @@
+use std::collections::{HashMap, HashSet};
+
+use itertools::Itertools;
+
+// NOTE: PartialOrd and Ord have no sense, but it is needed to sort them somehow
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+struct Cube {
+    t: usize,
+    f: usize,
+}
+
+impl Cube {
+    fn cost(&self) -> usize {
+        self.t.count_ones() as usize + self.f.count_ones() as usize
+    }
+
+    fn covers(&self, minterm: usize) -> bool {
+        let mask = self.t | self.f;
+        minterm & mask == self.t && !minterm & mask == self.f
+    }
+
+    fn combine(&self, other: &Self) -> Option<Self> {
+        let dt = self.t ^ other.t;
+        let df = self.f ^ other.f;
+
+        if dt == df && dt.count_ones() == 1 {
+            Some(Self {
+                t: self.t & other.t,
+                f: self.f & other.f,
+            })
+        } else {
+            None
+        }
+    }
+}
+
+fn cube_to_string(n: usize, cube: &Cube) -> String {
+    let mut s = String::new();
+
+    let Cube { mut t, mut f } = *cube;
+    for _ in 0..n {
+        match (t & 1, f & 1) {
+            (1, 0) => s.push('1'),
+            (0, 1) => s.push('0'),
+            (0, 0) => s.push('x'),
+            _ => unreachable!(),
+        }
+
+        t >>= 1;
+        f >>= 1;
+    }
+
+    s.chars().rev().collect()
+}
+
+fn cube_to_var_string(vars: &[&str], cube: &Cube) -> String {
+    let mut used_vars: Vec<String> = Vec::with_capacity(vars.len());
+
+    let Cube { mut t, mut f } = *cube;
+    for i in (0..vars.len()).rev() {
+        match (t & 1, f & 1) {
+            (1, 0) => used_vars.push(vars[i].into()),
+            (0, 1) => used_vars.push(format!("{}'", vars[i])),
+            (0, 0) => (),
+            _ => unreachable!(),
+        }
+
+        t >>= 1;
+        f >>= 1;
+    }
+
+    used_vars.into_iter().rev().join(" * ")
+}
+
+fn minimize_prime_implicants(n: usize, minterms: &[usize], maxterms: &[usize]) -> Vec<Cube> {
+    let minterms_set: HashSet<_> = minterms.iter().copied().collect();
+    let maxterms_set: HashSet<_> = maxterms.iter().copied().collect();
+
+    let mut anyterms_set = HashSet::new();
+    for i in 0..2usize.pow(n as u32) {
+        if !minterms_set.contains(&i) && !maxterms_set.contains(&i) {
+            anyterms_set.insert(i);
+        }
+    }
+
+    let mask = (1 << n) - 1;
+    let initial_cubes: Vec<_> = minterms_set
+        .union(&anyterms_set)
+        .sorted()
+        .map(|&i| Cube { t: i, f: !i & mask })
+        .collect();
+
+    let mut covered = vec![vec![false; initial_cubes.len()]];
+    let mut cubes = vec![initial_cubes];
+
+    for iteration in 0..n {
+        let current_covered = &mut covered[iteration];
+        let current_cubes = &cubes[iteration];
+
+        let mut new_cubes = HashSet::new();
+        for i in 0..current_cubes.len() {
+            for j in i + 1..current_cubes.len() {
+                let a = &current_cubes[i];
+                let b = &current_cubes[j];
+
+                if let Some(combined_cube) = a.combine(b) {
+                    current_covered[i] = true;
+                    current_covered[j] = true;
+                    new_cubes.insert(combined_cube);
+                }
+            }
+        }
+
+        covered.push(vec![false; new_cubes.len()]);
+        cubes.push(new_cubes.into_iter().collect());
+    }
+
+    let mut final_cubes = vec![];
+    for (iteration, iteration_cubes) in cubes.into_iter().enumerate() {
+        for (i, cube) in iteration_cubes.into_iter().enumerate() {
+            if !covered[iteration][i] {
+                final_cubes.push(cube);
+            }
+        }
+    }
+
+    final_cubes.sort();
+    final_cubes
+}
+
+fn print_prime_implicants_table(n: usize, minterms: &[usize], prime_implicants: &[Cube]) {
+    println!("Prime implicants:");
+    for (i, prime_implicant) in prime_implicants.iter().enumerate() {
+        let cube_str = cube_to_string(n, prime_implicant);
+        println!("{i}: {cube_str}");
+    }
+
+    println!();
+    println!("Prime Implicants Table (PIT):");
+    print!(" ");
+    println!(
+        "{}",
+        (0..minterms.len())
+            .map(|i| format!(" {} ", minterms[i]))
+            .join("")
+    );
+    for (i, prime_implicant) in prime_implicants.iter().enumerate() {
+        print!("{i}");
+        for &minterm in minterms {
+            if prime_implicant.covers(minterm) {
+                print!(" x ");
+            } else {
+                print!("   ");
+            }
+        }
+        println!();
+    }
+}
+
+fn solve_prime_implicants_table(minterms: &[usize], prime_implicants: &[Cube]) -> Vec<Cube> {
+    let mut table: HashSet<(usize, usize)> = (0..prime_implicants.len())
+        .cartesian_product(0..minterms.len())
+        .filter(|&(i, j)| prime_implicants[i].covers(minterms[j]))
+        .collect();
+
+    let mut selected_implicants = vec![false; prime_implicants.len()];
+    loop {
+        // Select essential minterms
+        let mut minterms_freq = vec![0; minterms.len()];
+        table.iter().for_each(|&(_, j)| minterms_freq[j] += 1);
+        table
+            .iter()
+            .for_each(|&(i, j)| selected_implicants[i] |= minterms_freq[j] == 1);
+
+        // Check if minterms are fully covered
+        let mut covered_minterms = vec![false; minterms.len()];
+        table
+            .iter()
+            .filter(|&&(i, _)| selected_implicants[i])
+            .for_each(|&(_, j)| covered_minterms[j] = true);
+        if table.is_empty() || covered_minterms.iter().all(|&v| v) {
+            break;
+        }
+
+        // Removing essential implicants
+        let new_table: HashSet<_> = table
+            .iter()
+            .filter(|&&(i, j)| !selected_implicants[i] && !covered_minterms[j])
+            .cloned()
+            .collect();
+        table = new_table;
+
+        if table.is_empty() {
+            // All implicants are used
+            break;
+        }
+
+        // Finding minterm coverage by implicants
+        let mut implicants = HashSet::new();
+        let mut covered_by_implicants: HashMap<usize, HashSet<_>> = HashMap::new();
+        table.iter().for_each(|&(i, j)| {
+            implicants.insert(i);
+            covered_by_implicants.entry(i).or_default().insert(j);
+        });
+
+        // Removing implicants by cost when essentials are not found
+        // NOTE: when checking combinations, implicants must be sorted, to give constant result
+        // (If not, it will variate due to order in HashSet)
+        let mut removed = false;
+        let mut implicants_to_remove = vec![false; prime_implicants.len()];
+        for (a, b) in implicants.iter().sorted().tuple_combinations() {
+            let a_set = &covered_by_implicants[a];
+            let b_set = &covered_by_implicants[b];
+            let eq = a_set == b_set;
+
+            let a_cost = prime_implicants[*a].cost();
+            let b_cost = prime_implicants[*b].cost();
+
+            if eq && a_cost >= b_cost {
+                implicants_to_remove[*a] = true;
+                removed = true;
+            } else if eq {
+                implicants_to_remove[*b] = true;
+                removed = true;
+            }
+        }
+
+        if removed {
+            let new_table: HashSet<_> = table
+                .iter()
+                .filter(|&&(i, _)| !implicants_to_remove[i])
+                .cloned()
+                .collect();
+            table = new_table;
+        } else {
+            // We can't remove implicants by cost, have to choose by ourselves.
+            // NOTE: this leads to non-minimal solution
+            // NOTE: this SHOULD NOT happen, as we are filtering equal implicant costs too
+            todo!()
+        }
+    }
+
+    prime_implicants
+        .iter()
+        .zip(selected_implicants)
+        .filter(|&(_, select)| select)
+        .map(|(cube, _)| cube)
+        .copied()
+        .collect()
+}
+
+fn minimize(n: usize, minterms: &[usize], maxterms: &[usize]) -> Vec<Cube> {
+    let prime_implicants = minimize_prime_implicants(n, minterms, maxterms);
+    print_prime_implicants_table(n, minterms, &prime_implicants);
+    solve_prime_implicants_table(minterms, &prime_implicants)
+}
+
 fn main() {
-    println!("Hello, world!");
+    let vars = ["X4", "X3", "X2", "X1"];
+    let minterms = [0, 1, 2, 3, 4]; // Термы со значением 1
+    let maxterms = [5, 6, 7, 8, 9]; // Термы со значением 0
+
+    let min_cubes = minimize(4, &minterms, &maxterms);
+
+    println!("Итоговые термы: ");
+    for cube in min_cubes {
+        println!(
+            "{} -> {}",
+            cube_to_string(4, &cube),
+            cube_to_var_string(&vars, &cube)
+        );
+    }
 }