Safe Haskell	Safe-Inferred
Language	Haskell98

Combinatorics.Permutation.WithoutSomeFixpoints

Synopsis

enumerate :: Eq a => Int -> [a] -> [[a]]
numbers :: Num a => [[a]]

Documentation

>>> import qualified Combinatorics.Permutation.WithoutSomeFixpoints as PermWOFP
>>> import qualified Combinatorics as Comb
>>> import qualified Test.QuickCheck as QC
>>> import Control.Applicative ((<$>))
>>> import Data.List (nub)
>>> 
>>> genPermutationWOFP :: QC.Gen (Int, String)
>>> genPermutationWOFP = do
>>> xs <- take 6 . nub <$> QC.arbitrary
>>> k <- QC.choose (0, length xs)
>>> return (k,xs)

enumerate :: Eq a => Int -> [a] -> [[a]] Source #

enumerate n xs list all permutations of xs where the first n elements do not keep their position (i.e. are no fixpoints).

This is a generalization of derangement.

Naive but comprehensible implementation.

numbers :: Num a => [[a]] Source #

http://oeis.org/A047920

QC.forAll genPermutationWOFP $ \(k,xs) -> PermWOFP.numbers !! length xs !! k == length (PermWOFP.enumerate k xs)

QC.forAll (QC.choose (0,100)) $ \k -> Comb.factorial (toInteger k) == PermWOFP.numbers !! k !! 0

QC.forAll (QC.choose (0,100)) $ \k -> Comb.derangementNumber (toInteger k) == PermWOFP.numbers !! k !! k