Create 251610 matrices as quickly as possible

Question

There are 251610 6 by 6 binary matrices that are inequivalent. We say two matrices are equivalent if there is some permutation of their rows and/or columns that makes them equal.

For example:

[1, 0, 0, 1, 0, 1]
[0, 0, 1, 1, 0, 1]
[1, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 1, 0]
[1, 1, 0, 0, 0, 1]
[1, 1, 0, 1, 0, 0]

and

[1, 1, 0, 1, 0, 0]
[1, 0, 0, 0, 1, 1]
[0, 1, 0, 1, 0, 1]
[1, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 1, 0]
[1, 0, 0, 1, 0, 1]

are equivalent but

[0, 1, 1, 1, 0, 0]
[0, 1, 0, 1, 1, 1]
[1, 1, 0, 0, 0, 1]
[1, 1, 0, 0, 1, 1]
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]

is not equivalent even though it has the same number of ones.

Task

Your code should output all 251610 inequivalent 6 by 6 matrices. You can choose which member of each equivalence class you output but you must only output one from each.

Scoring

I will time your code on my computer as long as it takes less than 60 minutes.

The timing machine

I will run your code in Ubuntu on a AMD Ryzen 5 3400G with 16GB of RAM.

Results

• 0.31 seconds by Anders Kaseorg in Rust (nightly build)
• 0.45 seconds by jdt in C++ (ported from Kaseorg)
• 18.57 seconds by Aspen in Python (ported from Kaseorg)

Answer 1

Rust, 0.27 s unofficial time

Compile with cargo build --release, run with target/release/matrices.

Cargo.toml

[package]
name = "matrices"
version = "0.1.0"
edition = "2021"

[dependencies]
fxhash = "0.2.1"

[profile.release]
lto = true

src/main.rs

use fxhash::FxHashSet;
use std::io::{BufWriter, StdoutLock, Write};

const ROWS: usize = 6;
const COLS: usize = 6;

fn transpose<const A: usize, const B: usize>(m: &[[bool; B]; A]) -> [[bool; A]; B] {
    let mut mt = [[false; A]; B];
    for j in 0..B {
        for i in 0..A {
            mt[j][i] = m[i][j];
        }
    }
    mt
}

fn found_permutations(
    m: &mut [[bool; COLS]; ROWS],
    row_sums: &[u32; ROWS],
    i: u32,
    permuted: bool,
    found: &mut FxHashSet<[[bool; COLS]; ROWS]>,
) {
    if i == ROWS as u32 {
        if permuted {
            let mut mt = transpose(m);
            mt.sort();
            let mtt = transpose(&mt);
            if mtt.is_sorted_by_key(|row| (row.iter().map(|&cell| cell as u32).sum::<u32>(), row)) {
                found.insert(mtt);
            }
        }
    } else {
        found_permutations(m, row_sums, i + 1, permuted, found);
        for i1 in i as usize + 1..ROWS {
            if row_sums[i1] != row_sums[i as usize] {
                break;
            }
            if &m[i1] != &m[i as usize] {
                m.swap(i as usize, i1);
                found_permutations(m, row_sums, i + 1, true, found);
                m.swap(i as usize, i1);
            }
        }
    }
}

fn search(
    m: &mut [[bool; COLS]; ROWS],
    mut i: u32,
    mut j: u32,
    mut row_sum: u32,
    mut min_row_sum: u32,
    mut equal_row: bool,
    equal_cols: &mut [bool; COLS],
    found: &mut FxHashSet<[[bool; COLS]; ROWS]>,
    stdout: &mut BufWriter<StdoutLock<'static>>,
) {
    if row_sum + COLS as u32 - j < min_row_sum {
        return;
    }
    if j == COLS as u32 {
        i += 1;
        if i == ROWS as u32 {
            if !found.remove(&*m) {
                let mut row_sums = [0; ROWS];
                for (row_sum, row) in row_sums.iter_mut().zip(&*m) {
                    *row_sum = row.iter().map(|&cell| cell as u32).sum::<u32>();
                }
                found_permutations(m, &row_sums, 0, false, found);
                for row in &*m {
                    for &cell in row {
                        stdout.write_all(if cell { b"1" } else { b"0" }).unwrap();
                    }
                    stdout.write_all(b" ").unwrap();
                }
                stdout.write_all(b"\n").unwrap();
            }
            return;
        }
        j = 0;
        min_row_sum = row_sum;
        row_sum = 0;
        equal_row = true;
    }
    let equal_col = equal_cols[j as usize];
    if !equal_col || !m[i as usize][j as usize - 1] {
        m[i as usize][j as usize] = false;
        equal_cols[j as usize] = equal_col && !m[i as usize][j as usize - 1];
        search(
            m,
            i,
            j + 1,
            row_sum,
            min_row_sum + (equal_row && m[i as usize - 1][j as usize]) as u32,
            equal_row && !m[i as usize - 1][j as usize],
            equal_cols,
            found,
            stdout,
        );
    }
    m[i as usize][j as usize] = true;
    equal_cols[j as usize] = equal_col && m[i as usize][j as usize - 1];
    search(
        m,
        i,
        j + 1,
        row_sum + 1,
        min_row_sum,
        equal_row && m[i as usize - 1][j as usize],
        equal_cols,
        found,
        stdout,
    );
    equal_cols[j as usize] = equal_col;
}

fn main() {
    let mut equal_cols = [true; COLS];
    equal_cols[0] = false;
    search(
        &mut [[false; COLS]; ROWS],
        0,
        0,
        0,
        0,
        false,
        &mut equal_cols,
        &mut FxHashSet::default(),
        &mut BufWriter::new(std::io::stdout().lock()),
    );
}

Answer 2

C++ (gcc), 0.38 seconds unofficial time

C++ port of @Ander Kaseorg's Rust code.

#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>
#include <array>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <chrono>

const int ROWS = 6;
const int COLS = 6;

using Matrix = std::array<std::array<bool, COLS>, ROWS>;
int count = 0;

// Optimized custom hash function for std::unordered_set of matrices
struct MatrixHash {
    size_t operator()(const Matrix& m) const {
        size_t hash = 0;
        for (const auto& row : m) {
            size_t rowHash = 0;
            for (bool cell : row) {
                rowHash = (rowHash << 1) | cell;
            }
            hash ^= rowHash + 0x9e3779b9 + (hash << 6) + (hash >> 2);
        }
        return hash;
    }
};

void found_permutations(Matrix& m, const std::array<uint32_t, ROWS>& row_sums, uint32_t i, bool permuted, std::unordered_set<Matrix, MatrixHash>& found) {
    if (i == ROWS) {
        if (permuted) {
            // transpose
            Matrix mt{};
            for (int j = 0; j < COLS; ++j) {
                for (size_t i = 0; i < ROWS; ++i) {
                    mt[j][i] = m[i][j];
                }
            }

            std::sort(mt.begin(), mt.end());
            // transpose
            Matrix mtt{};
            for (int j = 0; j < ROWS; ++j) {
                for (size_t i = 0; i < COLS; ++i) {
                    mtt[j][i] = mt[i][j];
                }
            }

            if (std::is_sorted(mtt.begin(), mtt.end(), [](const auto& row1, const auto& row2) {
                auto sum1 = std::accumulate(row1.begin(), row1.end(), 0u);
                auto sum2 = std::accumulate(row2.begin(), row2.end(), 0u);
                return std::tie(sum1, row1) < std::tie(sum2, row2);
                })) {
                found.insert(mtt);
            }
        }
    }
    else {
        found_permutations(m, row_sums, i + 1, permuted, found);
        for (size_t i1 = i + 1; i1 < ROWS; ++i1) {
            if (row_sums[i1] != row_sums[i]) {
                break;
            }
            if (m[i1] != m[i]) {
                std::swap(m[i], m[i1]);
                found_permutations(m, row_sums, i + 1, true, found);
                std::swap(m[i], m[i1]);
            }
        }
    }
}

// Search function
void search(Matrix& m, uint32_t i, uint32_t j, uint32_t row_sum, uint32_t min_row_sum, bool equal_row, std::array<bool, COLS>& equal_cols, std::unordered_set<Matrix, MatrixHash>& found, std::string& out) {
    if (row_sum + COLS - j < min_row_sum)
        return;

    if (j == COLS) {
        ++i;
        if (i == ROWS) {
            if (found.find(m) == found.end()) {
                std::array<uint32_t, ROWS> row_sums{};
                for (size_t r = 0; r < ROWS; ++r) {
                    row_sums[r] = std::accumulate(m[r].begin(), m[r].end(), 0u);
                }
                found_permutations(m, row_sums, 0, false, found);
                ++count;

                for (const auto& row : m) {
                    for (bool cell : row) {
                        out += cell ? '1' : '0';
                    }
                    out += ' ';
                }
                out += '\n';
            }
            return;
        }
        j = 0;
        min_row_sum = row_sum;
        row_sum = 0;
        equal_row = true;
    }

    bool equal_col = equal_cols[j];

    if (!equal_col || !m[i][j - 1]) {
        m[i][j] = false;
        equal_cols[j] = equal_col && !m[i][j - 1];
        search(m, i, j + 1, row_sum, min_row_sum + (equal_row && m[i - 1][j]), equal_row && !m[i - 1][j], equal_cols, found, out);
    }

    m[i][j] = true;
    equal_cols[j] = equal_col && m[i][j - 1];
    search(m, i, j + 1, row_sum + 1, min_row_sum, equal_row && m[i - 1][j], equal_cols, found, out);
    equal_cols[j] = equal_col;
}

// Main function
int main() {
    auto start = std::chrono::steady_clock::now();

    std::array<bool, COLS> equal_cols{};
    equal_cols.fill(true);
    equal_cols[0] = false;

    Matrix m{};
    std::unordered_set<Matrix, MatrixHash> found;

    std::string out;
    out.reserve(11000000);

    search(m, 0, 0, 0, 0, false, equal_cols, found, out);

    auto end = std::chrono::steady_clock::now();
    std::chrono::duration<double> elapsed = end - start;

    std::cout << "Count: " << count << '\n';
    std::cout << "Elapsed time: " << elapsed.count() << " seconds" << '\n';

    // std::cout << out;
}

Try it online!

Answer 3

Rust, 5.225 seconds unofficial time

Based on @Anders Kaseorg's Rust code, I made minor modification:

• add matrices count
• add timing
• user-defined is_sorted_by_key, so we don't need nightly release of rust

---

use fxhash::FxHashSet;
use std::io::{BufWriter, StdoutLock, Write};
use std::time::Instant;

const ROWS: usize = 6;
const COLS: usize = 6;

fn is_sorted_by_key(arr: &[[bool; COLS]; ROWS]) -> bool {
    for i in 1..ROWS {
        let prev_sum: u32 = arr[i - 1].iter().map(|&cell| cell as u32).sum();
        let curr_sum: u32 = arr[i].iter().map(|&cell| cell as u32).sum();
        if curr_sum < prev_sum || (curr_sum == prev_sum && arr[i] < arr[i - 1]) {
            return false;
        }
    }
    true
}

fn transpose<const A: usize, const B: usize>(m: &[[bool; B]; A]) -> [[bool; A]; B] {
    let mut mt = [[false; A]; B];
    for j in 0..B {
        for i in 0..A {
            mt[j][i] = m[i][j];
        }
    }
    mt
}

fn found_permutations(
    m: &mut [[bool; COLS]; ROWS],
    row_sums: &[u32; ROWS],
    i: u32,
    permuted: bool,
    found: &mut FxHashSet<[[bool; COLS]; ROWS]>,
) {
    if i == ROWS as u32 {
        if permuted {
            let mut mt: [[bool; 6]; 6] = transpose(m);
            mt.sort();
            let mtt: [[bool; 6]; 6] = transpose(&mt);

            if is_sorted_by_key(&mtt) {
                found.insert(mtt);
            }
        }
    } else {
        found_permutations(m, row_sums, i + 1, permuted, found);
        for i1 in i as usize + 1..ROWS {
            if row_sums[i1] != row_sums[i as usize] {
                break;
            }
            if &m[i1] != &m[i as usize] {
                m.swap(i as usize, i1);
                found_permutations(m, row_sums, i + 1, true, found);
                m.swap(i as usize, i1);
            }
        }
    }
}

fn search(
    m: &mut [[bool; COLS]; ROWS],
    mut i: u32,
    mut j: u32,
    mut row_sum: u32,
    mut min_row_sum: u32,
    mut equal_row: bool,
    equal_cols: &mut [bool; COLS],
    found: &mut FxHashSet<[[bool; COLS]; ROWS]>,
    stdout: &mut BufWriter<StdoutLock<'static>>,
    cnt: &mut u32,
) {
    if row_sum + COLS as u32 - j < min_row_sum {
        return;
    }
    if j == COLS as u32 {
        i += 1;
        if i == ROWS as u32 {
            if !found.remove(&*m) {
                let mut row_sums = [0; ROWS];
                for (row_sum, row) in row_sums.iter_mut().zip(&*m) {
                    *row_sum = row.iter().map(|&cell| cell as u32).sum::<u32>();
                }
                found_permutations(m, &row_sums, 0, false, found);
                for row in &*m {
                    for &cell in row {
                        stdout.write_all(if cell { b"1" } else { b"0" }).unwrap();
                    }
                    stdout.write_all(b" ").unwrap();
                }
                stdout.write_all(b"\n").unwrap();

                *cnt += 1; // Increment the count here
            }
            return;
        }
        j = 0;
        min_row_sum = row_sum;
        row_sum = 0;
        equal_row = true;
    }
    let equal_col = equal_cols[j as usize];
    if !equal_col || !m[i as usize][j as usize - 1] {
        m[i as usize][j as usize] = false;
        equal_cols[j as usize] = equal_col && !m[i as usize][j as usize - 1];
        search(
            m,
            i,
            j + 1,
            row_sum,
            min_row_sum + (equal_row && m[i as usize - 1][j as usize]) as u32,
            equal_row && !m[i as usize - 1][j as usize],
            equal_cols,
            found,
            stdout,
            cnt,
        );
    }
    m[i as usize][j as usize] = true;
    equal_cols[j as usize] = equal_col && m[i as usize][j as usize - 1];
    search(
        m,
        i,
        j + 1,
        row_sum + 1,
        min_row_sum,
        equal_row && m[i as usize - 1][j as usize],
        equal_cols,
        found,
        stdout,
        cnt,
    );
    equal_cols[j as usize] = equal_col;
}

fn main() {
    let mut equal_cols = [true; COLS];
    equal_cols[0] = false;
    let mut cnt = 0;

    let start = Instant::now();

    search(
        &mut [[false; COLS]; ROWS],
        0,
        0,
        0,
        0,
        false,
        &mut equal_cols,
        &mut FxHashSet::default(),
        &mut BufWriter::new(std::io::stdout().lock()),
        &mut cnt,
    );

    let duration = start.elapsed();

    println!("Total count: {}", cnt);
    println!("Execution time: {:?}", duration);
}

Answer 4

Python 3.12, 10.33 s unofficial time

Python port of @Ander Kaseorg's Rust code.

---

import sys
import time

ROWS = 6
COLS = 6

def is_sorted_by_key(arr):
    for i in range(1, ROWS):
        prev_sum = sum(arr[i - 1])
        curr_sum = sum(arr[i])
        if curr_sum < prev_sum or (curr_sum == prev_sum and arr[i] < arr[i - 1]):
            return False
    return True

def transpose(m):
    return [list(row) for row in zip(*m)]

def found_permutations(m, row_sums, i, permuted, found):
    if i == ROWS:
        if permuted:
            mt = transpose(m)
            mt.sort()
            mtt = transpose(mt)
            if is_sorted_by_key(mtt):
                mtt_tuple = tuple(tuple(row) for row in mtt)
                found.add(mtt_tuple)
    else:
        found_permutations(m, row_sums, i + 1, permuted, found)
        for i1 in range(i + 1, ROWS):
            if row_sums[i1] != row_sums[i]:
                break
            if m[i1] != m[i]:
                m[i], m[i1] = m[i1], m[i]
                found_permutations(m, row_sums, i + 1, True, found)
                m[i], m[i1] = m[i1], m[i]

def search(m, i, j, row_sum, min_row_sum, equal_row, equal_cols, found, stdout, cnt):
    if row_sum + (COLS - j) < min_row_sum:
        return
    if j == COLS:
        i += 1
        if i == ROWS:
            m_tuple = tuple(tuple(row) for row in m)
            if m_tuple not in found:
                row_sums = [sum(row) for row in m]
                found_permutations(m, row_sums, 0, False, found)
                for row in m:
                    stdout.write(''.join('1' if cell else '0' for cell in row) + ' ')
                stdout.write('\n')
                cnt[0] += 1
            return
        else:
            j = 0
            min_row_sum = row_sum
            row_sum = 0
            equal_row = True

    if i == 0 and j == 0:
        m[i][j] = False
        equal_cols_prev_j = equal_cols[j]
        equal_cols[j] = False
        search(m, i, j + 1, row_sum, min_row_sum, False, equal_cols, found, stdout, cnt)
        equal_cols[j] = equal_cols_prev_j

        m[i][j] = True
        equal_cols_prev_j = equal_cols[j]
        equal_cols[j] = False
        search(m, i, j + 1, row_sum + 1, min_row_sum, False, equal_cols, found, stdout, cnt)
        equal_cols[j] = equal_cols_prev_j

    elif i == 0:
        equal_col = equal_cols[j]
        if not equal_col or not m[i][j - 1]:
            m[i][j] = False
            prev_equal_cols_j = equal_cols[j]
            equal_cols[j] = equal_col and not m[i][j - 1]
            search(m, i, j + 1, row_sum, min_row_sum, False, equal_cols, found, stdout, cnt)
            equal_cols[j] = prev_equal_cols_j

        m[i][j] = True
        prev_equal_cols_j = equal_cols[j]
        equal_cols[j] = equal_col and m[i][j - 1]
        search(m, i, j + 1, row_sum + 1, min_row_sum, False, equal_cols, found, stdout, cnt)
        equal_cols[j] = prev_equal_cols_j

    elif j == 0:
        m[i][j] = False
        prev_equal_cols_j = equal_cols[j]
        equal_cols[j] = False
        m_i1_j = m[i - 1][j]
        search(m, i, j + 1, row_sum, min_row_sum + int(equal_row and m_i1_j), equal_row and not m_i1_j, equal_cols, found, stdout, cnt)
        equal_cols[j] = prev_equal_cols_j

        m[i][j] = True
        prev_equal_cols_j = equal_cols[j]
        equal_cols[j] = False
        m_i1_j = m[i - 1][j]
        search(m, i, j + 1, row_sum + 1, min_row_sum, equal_row and m_i1_j, equal_cols, found, stdout, cnt)
        equal_cols[j] = prev_equal_cols_j

    else:
        equal_col = equal_cols[j]
        m_i1_j = m[i - 1][j]
        if not equal_col or not m[i][j - 1]:
            m[i][j] = False
            prev_equal_cols_j = equal_cols[j]
            equal_cols[j] = equal_col and not m[i][j - 1]
            search(m, i, j + 1, row_sum, min_row_sum + int(equal_row and m_i1_j), equal_row and not m_i1_j, equal_cols, found, stdout, cnt)
            equal_cols[j] = prev_equal_cols_j

        m[i][j] = True
        prev_equal_cols_j = equal_cols[j]
        equal_cols[j] = equal_col and m[i][j - 1]
        search(m, i, j + 1, row_sum + 1, min_row_sum, equal_row and m_i1_j, equal_cols, found, stdout, cnt)
        equal_cols[j] = prev_equal_cols_j

def main():
    equal_cols = [True] * COLS
    equal_cols[0] = False
    cnt = [0]
    m = [[False] * COLS for _ in range(ROWS)]
    found = set()
    start = time.time()
    stdout = sys.stdout
    search(m, 0, 0, 0, 0, False, equal_cols, found, stdout, cnt)
    duration = time.time() - start
    print(f"Total count: {cnt[0]}")
    print(f"Execution time: {duration} seconds")

if __name__ == '__main__':
    main()