iota-0.1.0.0

Safe Haskell	Safe-Inferred
Language	GHC2021

Math.Combinatrics

Synopsis

newtype FactCache p = FactCache (Vector (GF p))
type HasFactCache (p :: Nat) = ?factCache :: FactCache p
newtype RecipFactCache p = RecipFactCache (Vector (GF p))
type HasRecipFactCache (p :: Nat) = ?recipFactCache :: RecipFactCache p
type HasCombCache (p :: Nat) = (HasFactCache p, HasRecipFactCache p)
fact :: (HasFactCache p, KnownNat p) => Int -> GF p
recipFact :: (HasRecipFactCache p, KnownNat p) => Int -> GF p
perm :: (HasFactCache p, HasRecipFactCache p, KnownNat p) => Int -> Int -> GF p
comb :: (HasFactCache p, HasRecipFactCache p, KnownNat p) => Int -> Int -> GF p
combNaive :: Int -> Int -> Int
buildFactCache :: forall p. KnownNat p => Int -> FactCache p
withFactCache :: forall p r. KnownNat p => Int -> (HasFactCache p => r) -> r
buildRecipFactCache :: forall p. (HasFactCache p, KnownNat p) => Int -> RecipFactCache p
withRecipFactCache :: forall p r. (HasFactCache p, KnownNat p) => Int -> (HasRecipFactCache p => r) -> r
withCombCache :: forall p r. KnownNat p => Int -> (HasCombCache p => r) -> r
combSmall :: forall p. KnownNat p => Int -> Int -> GF p
combSmallTable :: forall p. KnownNat p => Vector (GF p)

Documentation

newtype FactCache p Source #

Constructors

FactCache (Vector (GF p))

type HasFactCache (p :: Nat) = ?factCache :: FactCache p Source #

newtype RecipFactCache p Source #

Constructors

RecipFactCache (Vector (GF p))

type HasRecipFactCache (p :: Nat) = ?recipFactCache :: RecipFactCache p Source #

type HasCombCache (p :: Nat) = (HasFactCache p, HasRecipFactCache p) Source #

fact :: (HasFactCache p, KnownNat p) => Int -> GF p Source #

O(1)

>>> :set -XDataKinds
>>> withFactCache @1000000007 10 $ fact 10
3628800

recipFact :: (HasRecipFactCache p, KnownNat p) => Int -> GF p Source #

O(1)

perm :: (HasFactCache p, HasRecipFactCache p, KnownNat p) => Int -> Int -> GF p Source #

O(1)

n < p

comb :: (HasFactCache p, HasRecipFactCache p, KnownNat p) => Int -> Int -> GF p Source #

O(1)

n < p

combNaive :: Int -> Int -> Int Source #

O(r)

>>> combNaive 64 32
1832624140942590534
>>> combNaive 123456789 2
7620789313366866
>>> combNaive 123 456
0

buildFactCache :: forall p. KnownNat p => Int -> FactCache p Source #

withFactCache :: forall p r. KnownNat p => Int -> (HasFactCache p => r) -> r Source #

buildRecipFactCache :: forall p. (HasFactCache p, KnownNat p) => Int -> RecipFactCache p Source #

withRecipFactCache :: forall p r. (HasFactCache p, KnownNat p) => Int -> (HasRecipFactCache p => r) -> r Source #

withCombCache :: forall p r. KnownNat p => Int -> (HasCombCache p => r) -> r Source #

combSmall :: forall p. KnownNat p => Int -> Int -> GF p Source #

Lucas's theorem

O(log N)

combSmallTable :: forall p. KnownNat p => Vector (GF p) Source #

O(p ^ 2)