-- | Calculs d’arrangements.
module Htirage.Sequence where

import Data.Bool
import Data.Foldable (any, foldr)
import Data.Functor ((<$>))
import Data.List (length)
import Data.Ord (Ord(..))
import Prelude (Integral(..), Num(..), undefined)

-- | @'nAk' n k@ retourne le nombre de combinaisons
-- de longueur 'k' d’un ensemble de longueur 'n'.
nAk :: Integral i => i -> i -> i
n`nAk`k | n<0||k<0||n<k = undefined
        | otherwise     = go 1 1
        where
        go i acc = if k < i then acc else go (i+1) (acc * (n-i+1))

sequenceOfRank :: Integral i => i -> i -> i -> [i]
sequenceOfRank n k rk | rk<0||n`nAk`k<rk = undefined
                      | otherwise = shiftPositions (for1K 1 rk (n`nAk`k))
        where
        for1K i r a =
                if k < i then []
                else q+1 : for1K (i+1) r' a'
                where
                -- Optimized computation of: n-i`nAk`k-i
                a' = a `div` (n-i+1)
                -- Greatest multiple of 'a' lower or equal to the rank 'r',
                -- and the remaining of the rank
                (q, r') = r `divMod` a'
        shiftPositions = -- Promote the positions in the good interval.
                foldr (\x acc -> x : ((\x' -> if x' >= x then x'+1 else x') <$> acc)) []

rankOfSequence :: Integral i => i -> [i] -> i
rankOfSequence n ns | any (\x -> x<1||n<x) ns || n<k = undefined
                    | otherwise = for0K 1 0 (n`nAk`k) ns
        where
        k = fromInteger (toInteger (length ns))
        for0K _ r _ []     = r
        for0K i r a (x:xs) = for0K (i+1) r' a' xs'
                where
                -- Optimized computation of: n-i`nAk`k-i
                a' = a `div` (n-i+1)
                -- Next rank
                r' = r + (x-1) * a'
                xs' = (\x' -> if x < x' then x'-1 else x') <$> xs