Faster sorting network counting

Cargo.toml

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

[dependencies]
hashbrown = "0.13.2"
rustc-hash = "1.1.0"
typed-arena = "2.0.2"

main.rs

use typed_arena::Arena;
use rustc_hash::FxHasher;
use std::hash::BuildHasherDefault;
type HashSet<V> = hashbrown::HashSet<V, BuildHasherDefault<FxHasher>>;

type Item = u64;
const LOG_BITS: usize = Item::BITS.trailing_zeros() as usize;

fn search<'a>(
    arena: &'a Arena<Item>,
    found: &mut HashSet<&'a [Item]>,
    state: &mut [Item],
    last_i: usize,
    last_j: usize,
) {
    let n = state.len();
    for i in 0..n - 1 {
        let p = state[i];
        for j in i + 1..n {
            if i < last_i && j != last_i && j != last_j {
                continue;
            }
            let q = state[j];
            if p & !q != 0 {
                state[i] = p & q;
                state[j] = p | q;
                let mut inserted = false;
                let trim_state = &state[..n - 1];
                found.get_or_insert_with(trim_state, |trim_state| {
                    inserted = true;
                    arena.alloc_extend(trim_state.iter().copied())
                });
                if inserted {
                    search(arena, found, state, i, j);
                }
                state[i] = p;
                state[j] = q;
            }
        }
    }
}
fn count_networks(n: usize) -> usize {
    assert!(n <= LOG_BITS);
    let mut state = Vec::from_iter((0..n).map(|i| !0 / (1 << (1 << i) | 1)));
    let arena = Arena::new();
    let mut found = HashSet::default();
    found.insert(&*arena.alloc_extend(state.iter().take(n - 1).copied()));
    search(&arena, &mut found, &mut state, 0, 0);
    found.len()
}

fn main() {
    for n in 1..=LOG_BITS {
        println!("{}", count_networks(n));
    }
}