Rust

A port of Mr. Xcoder's example Python code. Naive brute force, so slow.

src/main.rs

extern crate permutohedron;
extern crate num_bigint;
extern crate num_traits;

use permutohedron::Heap;
use num_bigint::BigInt;
use num_traits::pow::Pow;
use num_traits::identities::One;
use num_traits::identities::Zero;

fn hafnian(matrix: Vec<Vec<i32>>) -> BigInt {
    let mut my_sum = BigInt::zero();
    let n = matrix.len() / 2;
    let mut data: Vec<usize> = (0..n*2).collect();
    let heap: Heap<'_, Vec<usize>, usize> = Heap::new(&mut data);

    for permutation in heap {
        let mut prod = BigInt::one();
        for j in 0..n {
            prod *= BigInt::from(matrix[permutation[2*j]][permutation[2*j+1]]);
        }
        my_sum += prod;
    }

    let factorial_n = (1..=n).fold(BigInt::one(), |f, i| f * BigInt::from(i));
    my_sum / (factorial_n * BigInt::from(2).pow(n as u32))
}

fn main() {
    println!("{:?}", hafnian(vec![
        vec![-1, 1, 1, -1, 0, 0, 1, -1], 
        vec![1, 0, 1, 0, -1, 0, -1, -1], 
        vec![1, 1, -1, 1, -1, -1, 0, -1], 
        vec![-1, 0, 1, -1, -1, 1, -1, 0], 
        vec![0, -1, -1, -1, -1, 0, 0, -1], 
        vec![0, 0, -1, 1, 0, 0, 1, 1], 
        vec![1, -1, 0, -1, 0, 1, 1, 0], 
        vec![-1, -1, -1, 0, -1, 1, 0, 1]
    ]));

    
    println!("{:?}", hafnian(vec![
        vec![1, 1, 0, 0, 0, 0, 0, 1, 0, 0], 
        vec![1, 1, -1, 0, -1, 1, 1, 1, 0, -1], 
        vec![0, -1, -1, -1, 0, -1, -1, 0, -1, 1], 
        vec![0, 0, -1, 1, -1, 1, -1, 0, 1, -1], 
        vec![0, -1, 0, -1, -1, -1, -1, 1, -1, 1], 
        vec![0, 1, -1, 1, -1, 1, -1, -1, 1, -1], 
        vec![0, 1, -1, -1, -1, -1, 1, 0, 0, 0], 
        vec![1, 1, 0, 0, 1, -1, 0, 1, 1, -1], 
        vec![0, 0, -1, 1, -1, 1, 0, 1, 1, 1], 
        vec![0, -1, 1, -1, 1, -1, 0, -1, 1, 1]
    ]));
    

    println!("{:?}", hafnian(vec![
        vec![-1, 0, -1, -1, 0, -1, 0, 1, -1, 0, 0, 0], 
        vec![0, 0, 0, 0, 0, -1, 0, 1, -1, -1, -1, -1], 
        vec![-1, 0, 0, 1, 0, 0, 0, 1, -1, 1, -1, 0], 
        vec![-1, 0, 1, -1, 1, -1, -1, -1, 0, -1, -1, -1], 
        vec![0, 0, 0, 1, 0, 0, 0, 0, 0, 1, -1, 0], 
        vec![-1, -1, 0, -1, 0, 0, 1, 1, 1, 1, 1, 0],
        vec![0, 0, 0, -1, 0, 1, 1, -1, -1, 0, 1, 0],
        vec![1, 1, 1, -1, 0, 1, -1, 1, -1, -1, -1, -1], 
        vec![-1, -1, -1, 0, 0, 1, -1, -1, -1, 1, -1, 0], 
        vec![0, -1, 1, -1, 1, 1, 0, -1, 1, -1, 1, 1], 
        vec![0, -1, -1, -1, -1, 1, 1, -1, -1, 1, 0, -1], 
        vec![0, -1, 0, -1, 0, 0, 0, -1, 0, 1, -1, 1]
    ]));


    println!("{:?}", hafnian(vec![
        vec![-1, 1, 0, 1, 0, -1, 0, 0, -1, 1, -1, 1, 0, -1], 
        vec![1, -1, 1, -1, 1, 1, -1, 0, -1, 1, 1, 0, 0, -1], 
        vec![0, 1, 1, 1, -1, 1, -1, -1, 0, 0, -1, 0, -1, -1], 
        vec![1, -1, 1, -1, 1, 0, 1, 1, -1, -1, 0, 0, 1, 1], 
        vec![0, 1, -1, 1, 0, 1, 0, 1, -1, -1, 1, 1, 0, -1], 
        vec![-1, 1, 1, 0, 1, 1, -1, 0, 1, -1, -1, -1, 1, -1], 
        vec![0, -1, -1, 1, 0, -1, -1, -1, 0, 1, -1, 0, 1, -1], 
        vec![0, 0, -1, 1, 1, 0, -1, 0, 0, -1, 0, 0, 0, 1], 
        vec![-1, -1, 0, -1, -1, 1, 0, 0, 1, 1, 0, 1, -1, 0], 
        vec![1, 1, 0, -1, -1, -1, 1, -1, 1, 1, 1, 0, 1, 0], 
        vec![-1, 1, -1, 0, 1, -1, -1, 0, 0, 1, -1, 0, -1, 0], 
        vec![1, 0, 0, 0, 1, -1, 0, 0, 1, 0, 0, 1, 1, 1], 
        vec![0, 0, -1, 1, 0, 1, 1, 0, -1, 1, -1, 1, 1, -1], 
        vec![-1, -1, -1, 1, -1, -1, -1, 1, 0, 0, 0, 1, -1, -1]
    ]));

}

Cargo.toml

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

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
# rand = "0.8.0"
# hyper = "0.13"
# tokio = { version = "0.2", features = ["full"] }
# rayon = "1.5.1"
# ndarray = "0.15.4"
# statrs = "0.13.0"
# ndarray-stats = "0.4.0"
# ndarray-linalg = "0.15"
# bitvec = "1.0.1"
# uint = "0.9"
# pariter = "0.5.1"
# rug = { version = "1.19.0", features = ["integer"], default-features = false }
# kd-tree = "0.5.1"
# time = "0.3"

permutohedron = "0.2.4"
num-bigint = "0.3.3"
num-traits = "0.2.14"

Build and running

# win10 environment

$ cargo  build
$ target\debug\rust_hello.exe
BigInt { sign: Plus, data: BigUint { data: [4] } }
BigInt { sign: Minus, data: BigUint { data: [13] } }
......