-- | 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