Htirage.Combin

Calculs de combinaisons.

Documentation

nCk :: Integral i => i -> i -> i

nnCkk retourne le nombre de combinaisons de longueur k d’un ensemble de longueur n.

combinOfRank :: Integral i => i -> i -> i -> [i]

combinOfRank n k r retourne les indices de permutation de la combinaison de k entiers parmi [1..n] au rang lexicographique r dans [0..(nnCkk)-1].

Construit chaque choix de la combinaison en prenant le prochain plus grand 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

rankOfCombin :: Integral i => i -> [i] -> i

rankOfCombin n ns retourne le rang lexicographique dans [0..(nnCklength ns)-1] 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, pp.24-25

rankOfCombin n . combinOfRank n k == id
combinOfRank n k . rankOfCombin n == id

permute :: [Int] -> [a] -> [a]

permute ps xs remplace chaque élément de ps par l’élement qu’il indexe dans xs entre [1..length xs].