| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell98 |
Combinatorics.Permutation.WithoutSomeFixpoints
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 #
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