combinat-0.2.9.0: Generate and manipulate various combinatorial objects.

Safe HaskellNone
LanguageHaskell2010

Math.Combinat.Sets

Contents

Description

Subsets.

Synopsis

Choices

choose_ :: Int -> Int -> [[Int]] Source #

choose_ k n returns all possible ways of choosing k disjoint elements from [1..n]

choose_ k n == choose k [1..n]

choose :: Int -> [a] -> [[a]] Source #

All possible ways to choose k elements from a list, without repetitions. "Antisymmetric power" for lists. Synonym for kSublists.

choose' :: Int -> [a] -> [([a], [a])] Source #

A version of choose which also returns the complementer sets.

choose k = map fst . choose' k

choose'' :: Int -> [(a, b)] -> [([a], [b])] Source #

Another variation of choose'. This satisfies

choose'' k == map (\(xs,ys) -> (map fst xs, map snd ys)) . choose' k

chooseTagged :: Int -> [a] -> [[Either a a]] Source #

Another variation on choose which tags the elements based on whether they are part of the selected subset (Right) or not (Left):

choose k = map rights . chooseTagged k

Compositions

combine :: Int -> [a] -> [[a]] Source #

All possible ways to choose k elements from a list, with repetitions. "Symmetric power" for lists. See also Math.Combinat.Compositions. TODO: better name?

compose :: Int -> [a] -> [[a]] Source #

A synonym for combine.

Tensor products

tuplesFromList :: Int -> [a] -> [[a]] Source #

"Tensor power" for lists. Special case of listTensor:

tuplesFromList k xs == listTensor (replicate k xs)

See also Math.Combinat.Tuples. TODO: better name?

listTensor :: [[a]] -> [[a]] Source #

"Tensor product" for lists.

Sublists

kSublists :: Int -> [a] -> [[a]] Source #

Sublists of a list having given number of elements. Synonym for choose.

sublists :: [a] -> [[a]] Source #

All sublists of a list.

countKSublists :: Int -> Int -> Integer Source #

# = binom { n } { k }.

Random choice

randomChoice :: RandomGen g => Int -> Int -> g -> ([Int], g) Source #

randomChoice k n returns a uniformly random choice of k elements from the set [1..n]

Example:

do
  cs <- replicateM 10000 (getStdRandom (randomChoice 3 7))
  mapM_ print $ histogram cs