-- | Calculs combinatoires.
module Htirage.Combinatorics where

-- | @n`nCk`k@ retourne le nombre de combinaisons
-- de longueur 'k' d’un ensemble de longueur 'n'.
nCk :: Integral i => i -> i -> i
n`nCk`k | k == 0        = 1
        | k > n `div` 2 = n`nCk`(n - k) -- more efficient and safe with smaller numbers
        | otherwise     = (n`nCk`(k - 1)) * (n - k + 1) `div` k

-- | @combOfRank n k r@ retourne les indices de permutation
-- de la combinaison de 'k' entiers parmi @[1..n]@
-- au rang lexicographique 'r'.
-- 
-- Construit chaque choix de la combinaison en prenant le prochain plus petit
-- dont le successeur engendre un nombre de combinaisons
-- qui dépasse le rang restant à atteindre.
--
-- DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, p.26
combOfRank :: Integral i => Show i => i -> i -> i -> [i]
combOfRank n k = for1K 1 1 where
	for1K i j r | i <  k    = uptoRank i j r
	            | i == k    = [j+r] -- because when i == k, nbCombs is always 1
	            | otherwise = []
	uptoRank i j r | nbCombs <- (n-j)`nCk`(k-i)
	               , nbCombs <= r = uptoRank i (j+1) (r-nbCombs)
	               | otherwise    = j : for1K (i+1) (j+1) r

-- | @rankOfComb n ns@ retourne le rang lexicographique
-- de la combinaison 'ns' d’entiers parmi @[1..n]@.
--
-- Compte le nombre de combinaisons précédant celle de rang 'r'.
--
-- DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, p.26
--
-- @rankOfComb n . combOfRank n k == id@
-- @combOfRank n k . rankOfComb n == id@
rankOfComb :: Integral i => i -> [i] -> i
rankOfComb n ns = for1K 1 0 0 ns where
	k = fromInteger (toInteger (length ns))
	for1K _ r _ []      = r
	for1K i r x1 (x:xs) = for1K (i+1) r' x xs
		where r' = r + sum [ (n-j)`nCk`(k-i)
		                   | j <- [x1+1..x-1]
		                   ]

-- | @permute ps xs@ remplace chaque élément de 'ps'
-- par l’élement qu’il indexe dans 'xs' entre @[1..length xs]@.
permute :: [Int] -> [a] -> [a]
permute ps xs = [xs !! pred p | p <- ps]

{- Implémentations alternatives

-- | @n`nAk`k@ retourne le nombre d’arrangements de longueur 'k' d’une liste de longueur 'n'.
nAk :: Integral i => i -> i -> i
n`nAk`k = product [n-k+1 .. n]

-- | @n`nCk`k@ retourne le nombre de combinaisons
-- de longueur 'k' d’une liste de longueur 'n'.
nCk :: Integral i => i -> i -> i
n`nCk`k | k > n `div` 2 = n`nCk`(n-k) -- more efficient with smaller numbers
        | otherwise     = n`nAk`k `div` product [1..k]


-- | @combs k xs@ retourne les combinaisons de longueur 'k' d’une liste 'xs'.
combs :: Int -> [a] -> [[a]]
combs 0 _      = [[]]
combs _ []     = []
combs k (x:xs) = combs k xs ++
                 (x :) `map` combs (k - 1) xs

-- | @combs k xs@ retourne les combinaisons
-- de longueur 'k' des éléments de la liste 'xs'.
combs :: Int -> [a] -> [[a]]
combs k xs = combsK xs !! (length xs - k)

-- | @combsK xs@ retourne toutes les combinaisons
-- de longueur allant de @length xs@ à 0 de la liste 'xs',
-- 
-- Algorithme dynamique permettant un calcul de 'combs'
-- relativement rapide du fait du partage de 'combsKmoins1'.
combsK :: [a] -> [[[a]]]
combsK [] = [[[]]]
combsK (x : xs) =
	zipWith (++) ([] : combsKmoins1)
	             (map (map (x :)) combsKmoins1 ++ [[]])
	where combsKmoins1 = combsK xs
-}