Counting nonsense

bitotal_relations.rs

use std::collections::HashMap;

fn main() {
    println!("Counting bitotal relations R: 1..n |<>| 1..m");
    println!("i.e. id <= R ; R^T and id <= R^T ; R");
    println!("(see: https://en.wikipedia.org/wiki/Relation_algebra, book: Algebra of Programming by Bird and Moore)");
    println!();
    println!("Equivalently, counting bipartite graphs between node sets of size n and m,");
    println!("where every vertex has degree at least 1.");
    println!();
    println!("Equivalently, counting n x m bit matrices with no all-zero rows or columns.");
    println!("...");

    let mut results = HashMap::new();

    let MAX = 12u8;

    for width in 0..MAX {
        for height in 0..MAX {
            // chosen experimentally to finish quickly
            if width * height > 29 {
                continue;
            }
            if results.contains_key(&(width, height)) {
                continue;
            }
            let result = count_bitotal_relations(width, height);
            println!(
                "| {} |<>| {} | = {} (/ {})",
                width,
                height,
                result,
                (2u64).pow((width * height) as u32)
            );
            results.insert((width, height), result);
            results.insert((height, width), result);
        }
    }

    println!("Result matrix (rows and columns start at 0)");
    println!("---------------------------------------------");

    for width in 0..MAX {
        for height in 0..MAX {
            if results.contains_key(&(width, height)) {
                print!("{: >11}", results[&(width, height)]);
            } else {
                print!("{: >11}", "");
            }
        }
        println!();
    }
}

/// Stores a rectangular bitarray inside a u64.
#[derive(Clone, Copy)]
struct BitArray {
    mask: u64,
    width: u8,
    height: u8,
}

impl BitArray {
    fn new(mask: u64, width: u8, height: u8) -> Self {
        assert!(width * height <= 64);
        BitArray {
            mask: mask,
            width: width,
            height: height,
        }
    }

    fn set_bit(&mut self, row: u8, col: u8) {
        let index = row * self.width + col;
        assert!(index < self.width * self.height);
        self.mask |= 1 << index;
    }

    fn get_bit(&self, width: u8, height: u8, row: u8, col: u8) -> bool {
        let index = row * width + col;
        assert!(index < width * height);
        (self.mask & (1 << index)) != 0
    }

    fn print_bits(&self) {
        for row in 0..self.height {
            for col in 0..self.width {
                if self.get_bit(self.width, self.height, row, col) {
                    print!("1");
                } else {
                    print!("_");
                }
            }
            println!();
        }
        //println!("({:032b})", self.mask);
    }
}

// count the number of relations R: 1..n <> 1..n
// s.t. id <= R ; R^T and id < R^T ; R
fn count_bitotal_relations(width: u8, height: u8) -> u64 {
    println!("checking width = {width}, height = {height}");

    if width == 0 || height == 0 {
        return 1;
    }

    println!("masks: ");
    // a relation is a bitmatrix.
    // just check that all rows and columns contain something.
    let mut to_check = vec![];
    for row in 0..height {
        let mut mask: BitArray = BitArray::new(0, width, height);
        for col in 0..width {
            mask.set_bit(row, col)
        }
        println!("---------------------");
        mask.print_bits();
        to_check.push(mask.mask);
    }
    for col in 0..width {
        let mut mask = BitArray::new(0, width, height);
        for row in 0..height {
            mask.set_bit(row, col);
        }
        println!("---------------------");
        mask.print_bits();
        to_check.push(mask.mask);
    }
    println!("---------------------");

    let max = (2u64).pow((width * height) as u32);
    for mask in &to_check {
        assert!(*mask < max);
    }

    let mut count = 0;
    for relation in 0..max {
        /*if n > 2 && relation % (max / 4) == 0 {
            println!("{} / {}...", relation, max);
        }*/
        /*if n < 3 {
            println!("\n\n");
            println!("{relation}...");
        }*/
        // let prev_count = count;
        count += 1;
        for mask in &to_check {
            if *mask & relation == 0 {
                /*if n < 3 {
                    println!("---------");
                    println!("MASK UNHIT! NOT BITOTAL!");
                    println!("MASK: ");
                    BitArray::new(*mask, n, n).print_bits();
                    println!("RELATION: ");
                    BitArray::new(relation, n, n).print_bits();
                }*/
                count -= 1;
                break;
            }
        }
        /*
        if n < 3 && prev_count < count {
            println!("---------");
            println!("ALL MASKS HIT! BITOTAL!");
            println!("RELATION: ");
            BitArray::new(relation, n, n).print_bits();
        }
        */
    }

    count
}

Output:

          1          1          1          1          1          1          1          1          1          1          1          1
          1          1          1          1          1          1          1          1          1          1          1          1
          1          1          7         25         79        241        727       2185       6559      19681      59047     177145
          1          1         25        265       2161      16081     115465     816985    5745121   40294561
          1          1         79       2161      41503     693601   10924399  167578321
          1          1        241      16081     693601   24997921
          1          1        727     115465   10924399
          1          1       2185     816985  167578321
          1          1       6559    5745121
          1          1      19681   40294561
          1          1      59047
          1          1     177145