Combinations and permutations: Difference between revisions

=={{header|Haskell}}==

The Haskell Integer type supports arbitrary precision so floating point approximation is not needed.

<lang haskell>perm :: Integer -> Integer -> Integer

perm n k = product [n-k+1..n]

comb :: Integer -> Integer -> Integer

comb n k = perm n k `div` product [1..k]

main :: IO ()

main = do

let showBig maxlen b =

let st = show b

stlen = length st

in if stlen < maxlen then st else take maxlen st ++ "... (" ++ show (stlen-maxlen) ++ " more digits)"

let showPerm pr =

putStrLn $ "perm(" ++ show n ++ "," ++ show k ++ ") = " ++ showBig 40 (perm n k)

where n = fst pr

k = snd pr

let showComb pr =

putStrLn $ "comb(" ++ show n ++ "," ++ show k ++ ") = " ++ showBig 40 (comb n k)

where n = fst pr

k = snd pr

putStrLn "A sample of permutations from 1 to 12:"

mapM_ showPerm [(n, n `div` 3) | n <- [1..12] ]

putStrLn ""

putStrLn "A sample of combinations from 10 to 60:"

mapM_ showComb [(n, n `div` 3) | n <- [10,20..60] ]

putStrLn ""

putStrLn "A sample of permutations from 5 to 15000:"

mapM_ showPerm [(n, n `div` 3) | n <- [5,50,500,1000,5000,15000] ]

putStrLn ""

putStrLn "A sample of combinations from 100 to 1000:"

mapM_ showComb [(n, n `div` 3) | n <- [100,200..1000] ]

</lang>

{{out}}

<pre style="font-size:80%">A sample of permutations from 1 to 12:

perm(1,0) = 1

perm(2,0) = 1

perm(3,1) = 3

perm(4,1) = 4

perm(5,1) = 5

perm(6,2) = 30

perm(7,2) = 42

perm(8,2) = 56

perm(9,3) = 504

perm(10,3) = 720

perm(11,3) = 990

perm(12,4) = 11880

A sample of combinations from 10 to 60:

comb(10,3) = 120

comb(20,6) = 38760

comb(30,10) = 30045015

comb(40,13) = 12033222880

comb(50,16) = 4923689695575

comb(60,20) = 4191844505805495

A sample of permutations from 5 to 15000:

perm(5,1) = 5

perm(50,16) = 103017324974226408345600000

perm(500,166) = 3534874921742942787609361826601762306844... (395 more digits)

perm(1000,333) = 5969326288503415089039701765900784280998... (932 more digits)

perm(5000,1666) = 6856745757255674275484536940248896062234... (5986 more digits)

perm(15000,5000) = 9649853988727493922014858805931295980792... (20430 more digits)

A sample of combinations from 100 to 1000:

comb(100,33) = 294692427022540894366527900

comb(200,66) = 7269752545169278341527066651192738976755... (14 more digits)

comb(300,100) = 4158251463258564744783383526326405580280... (42 more digits)

comb(400,133) = 1257948684182108702133348475651965004491... (70 more digits)

comb(500,166) = 3926028386194422755220408345072331428197... (97 more digits)

comb(600,200) = 2506017783221402805005616770513228835202... (125 more digits)

comb(700,233) = 8103203563339599904740453644031138232944... (152 more digits)

comb(800,266) = 2645623362683627034288829299556124255091... (180 more digits)

comb(900,300) = 1743356373296446642960730765085718347630... (208 more digits)

comb(1000,333) = 5776134553147651669777486323549601722339... (235 more digits)

</pre>