deep_causality_algorithms 0.4.0

Computational causality algorithms and utils used in the DeepCausality project.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

/*
 * SPDX-License-Identifier: MIT
 * Copyright (c) 2023 - 2026. The DeepCausality Authors and Contributors. All Rights Reserved.
 */

//! Factorials and the `rho` inclusion-exclusion recurrence.
//!
//! Ported from the authoritative `cliquepicking_rs::combinatorics`, made generic
//! over the count type `T`. The reference counts in `num_bigint::BigUint`; this
//! crate is dependency-free, so the count type is instead a generic
//! `T: RealField + FromPrimitive` (e.g. `f64` or `deep_causality_num::Float106`).
//!
//! Two functions live here:
//! * [`factorial`] — `k! = ∏_{i=1}^{k} i`, memoized.
//! * [`rho`] — the recurrence from the Clique-Picking paper that counts orderings
//!   of a clique avoiding the forbidden separator-extension prefixes. It is an
//!   inclusion-exclusion that **subtracts** terms; for that reason the count must
//!   stay in linear (not log) space, so this port keeps the subtraction exactly
//!   as in the reference.

use crate::dag_sampling::memoization::Memoization;
use deep_causality_algebra::RealField;
use deep_causality_num::FromPrimitive;

/// Converts a `usize` into the count type `T`. Counts arising here (small
/// integers and factorials) are representable in every supported `RealField`.
#[inline]
fn from_usize<T: FromPrimitive>(n: usize) -> T {
    <T as FromPrimitive>::from_usize(n).expect("count is representable in every RealField")
}

/// Returns `n!` as a value of `T`, memoized in `memoization` (`memoization[k]`
/// holds `k!` once computed; `None` means not yet computed).
pub(crate) fn factorial<T: RealField + FromPrimitive>(
    n: usize,
    memoization: &mut [Option<T>],
) -> T {
    if let Some(res) = memoization[n] {
        return res;
    }
    let mut result = T::one();
    for i in 1..n + 1 {
        result *= from_usize::<T>(i);
    }
    memoization[n] = Some(result);
    result
}

/// Evaluates the `rho` recurrence for the forbidden-size vector `x`, memoized by
/// `x` in `memoization.rho`.
///
/// Mirrors the reference exactly, including the **subtraction**:
/// `rho(x) = x[0]! - Σ_{i≥1} (x[0] - x[i])! * rho(x[i..])`.
/// The first element `x[0]` is assumed present (`x` is non-empty in every call
/// site).
pub(crate) fn rho<T: RealField + FromPrimitive>(
    x: &[usize],
    memoization: &mut Memoization<T>,
) -> T {
    let x_vec = x.to_vec();
    if let Some(res) = memoization.rho.get(&x_vec) {
        return *res;
    }
    let mut result = factorial(x[0], &mut memoization.factorial);
    for i in 1..x.len() {
        let lead = factorial(x[0] - x[i], &mut memoization.factorial);
        let tail = rho(&x[i..], memoization);
        result -= lead * tail;
    }
    memoization.rho.insert(x_vec, result);
    result
}