Trait malachite_base::num::arithmetic::traits::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>

Object Safety

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