Trait CheckedSubfactorial

pub trait CheckedSubfactorial: Sized {
    // Required method
    fn checked_subfactorial(n: u64) -> Option<Self>;
}

Computes the subfactorial of a u64, returning None if the result is too large to be represented. The subfactorial of a non-negative integer $n$ counts the number of derangements of $n$ elements, which are the permutations in which no element is fixed.

Required Methods

fn checked_subfactorial(n: u64) -> Option<Self>

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementations on Foreign Types

impl CheckedSubfactorial for u8

fn checked_subfactorial(n: u64) -> Option<u8>

Computes the subfactorial of a number.

The subfactorial of $n$ counts the number of derangements of a set of size $n$; a derangement is a permutation with no fixed points.

If the input is too large, the function returns None.

$$ f(n) = \begin{cases} \operatorname{Some}(!n) & \text{if} \quad !n < 2^W, \\ \operatorname{None} & \text{if} \quad !n \geq 2^W, \end{cases} $$ where $W$ is Self::WIDTH.

$!n = O(n!) = O(\sqrt{n}(n/e)^n)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl CheckedSubfactorial for u16

fn checked_subfactorial(n: u64) -> Option<u16>

Computes the subfactorial of a number.

The subfactorial of $n$ counts the number of derangements of a set of size $n$; a derangement is a permutation with no fixed points.

If the input is too large, the function returns None.

$$ f(n) = \begin{cases} \operatorname{Some}(!n) & \text{if} \quad !n < 2^W, \\ \operatorname{None} & \text{if} \quad !n \geq 2^W, \end{cases} $$ where $W$ is Self::WIDTH.

$!n = O(n!) = O(\sqrt{n}(n/e)^n)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl CheckedSubfactorial for u32

fn checked_subfactorial(n: u64) -> Option<u32>

Computes the subfactorial of a number.

The subfactorial of $n$ counts the number of derangements of a set of size $n$; a derangement is a permutation with no fixed points.

If the input is too large, the function returns None.

$$ f(n) = \begin{cases} \operatorname{Some}(!n) & \text{if} \quad !n < 2^W, \\ \operatorname{None} & \text{if} \quad !n \geq 2^W, \end{cases} $$ where $W$ is Self::WIDTH.

$!n = O(n!) = O(\sqrt{n}(n/e)^n)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl CheckedSubfactorial for u64

fn checked_subfactorial(n: u64) -> Option<u64>

Computes the subfactorial of a number.

The subfactorial of $n$ counts the number of derangements of a set of size $n$; a derangement is a permutation with no fixed points.

If the input is too large, the function returns None.

$$ f(n) = \begin{cases} \operatorname{Some}(!n) & \text{if} \quad !n < 2^W, \\ \operatorname{None} & \text{if} \quad !n \geq 2^W, \end{cases} $$ where $W$ is Self::WIDTH.

$!n = O(n!) = O(\sqrt{n}(n/e)^n)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl CheckedSubfactorial for u128

fn checked_subfactorial(n: u64) -> Option<u128>

Computes the subfactorial of a number.

The subfactorial of $n$ counts the number of derangements of a set of size $n$; a derangement is a permutation with no fixed points.

If the input is too large, the function returns None.

$$ f(n) = \begin{cases} \operatorname{Some}(!n) & \text{if} \quad !n < 2^W, \\ \operatorname{None} & \text{if} \quad !n \geq 2^W, \end{cases} $$ where $W$ is Self::WIDTH.

$!n = O(n!) = O(\sqrt{n}(n/e)^n)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

impl CheckedSubfactorial for usize

fn checked_subfactorial(n: u64) -> Option<usize>

Computes the subfactorial of a usize.

The subfactorial of $n$ counts the number of derangements of a set of size $n$; a derangement is a permutation with no fixed points.

If the input is too large, the function returns None.

$$ f(n) = \begin{cases} \operatorname{Some}(!n) & \text{if} \quad !n < 2^W, \\ \operatorname{None} & \text{if} \quad !n \geq 2^W, \end{cases} $$ where $W$ is usize::WIDTH.

$!n = O(n!) = O(\sqrt{n}(n/e)^n)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Implementors