Htirage.Combin

Calculs de combinaisons.

Documentation

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

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

Computed using the formula: nCk n (k+1) == nCk n (k-1) * (n-k+1) / k

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..nCk n k - 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..nCk n (length ns) - 1] de la combinaison ns d’entiers parmi [1..n].

WARNING: ns doit être triée de manière ascendante.

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 r) == r
combinOfRank n (length ns) (rankOfCombin n ns) == ns

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