Permutations/Derangements: Difference between revisions
→{{header|Haskell}}
(Added Kotlin) |
|||
Line 1,005:
=={{header|Haskell}}==
<lang Haskell>import Control.Monad (forM_)
import Data.List (permutations)
-- Compute all derangements of a list
derangements
derangements = (\x -> filter (and . zipWith (/=) x)) <*> permutations
-- Compute the number of derangements of n elements
subfactorial :: (Eq a, Num a) => a -> a
subfactorial 0 = 1
subfactorial 1 = 0
subfactorial n = (n - 1) * (subfactorial (n - 1) + subfactorial (n - 2))
main
main
-- Generate
= do
print $ derangements [1 .. 4]
putStrLn ""
-- Print the count of derangements vs subfactorial
forM_ [1 .. 9] $
\i ->
putStrLn $ show (length (derangements [1..i])) ++ " " ++ ▼
putStrLn $
putStrLn ""
-- Print the number of derangements in a list of 20 items
print $ subfactorial 20</lang>
<pre>[[4,3,2,1],[3,4,2,1],[2,3,4,1],[4,1,2,3],[2,4,1,3],[2,1,4,3],[4,3,1,2],[3,4,1,2],[3,1,4,2]]▼
▲{{out}}
▲[[4,3,2,1],[3,4,2,1],[2,3,4,1],[4,1,2,3],[2,4,1,3],[2,1,4,3],[4,3,1,2],[3,4,1,2],[3,1,4,2]]
0 0
Line 1,044 ⟶ 1,046:
133496 133496
895014631192902121</pre>
Alternatively, this is a backtracking method:
| |||