permutation-0.4.1: A library for permutations and combinations.

Stability experimental Patrick Perry

Data.Choose

Description

Immutable combinations.

Synopsis

# Combinations

data Choose Source

The immutable combination data type. A way of representing `k` unordered outcomes from `n` possiblities. The possibilites are represented as the indices `0, ..., n-1`, and the outcomes are given as a subset of size `k`. The subset is stored with the indices in ascending order.

Instances

 Eq Choose Show Choose

# Creating combinations

choose :: Int -> Int -> ChooseSource

`choose n k` returns the first combination of `k` outcomes from `n` possibilites, namely the subset `{ 0, ..., k-1 }`.

listChoose :: Int -> Int -> [Int] -> ChooseSource

Construct a combination from a list of elements. `listChoose n k is` creates a combination of `k` outcomes from `n` possibilities initialized to have the `i`th element equal to `is !! i`. For the combination to be valid, the elements must all be unique, they must be in sorted order, and they all must be in the range `0 .. n-1`.

# Accessing combination elements

at :: Choose -> Int -> IntSource

`at c i` gets the value of the `i`th element of the combination `c`. The index `i` must be in the range `0..(k-1)`, where `k` is the size of the combination.

# Combination properties

Get the number of possibilities, `n`.

Get the number of outcomes, `k`.

elems :: Choose -> [Int]Source

Get a list of the `k` outcomes.

# Combination functions

Get the inverse of a combination

complElems :: Choose -> [Int]Source

Get a list of the elements in the complement of a combination. If the combination is a subset of `k` outcomes from `n` possibilities, then the returned list will be sorted and of length `n-k`.

Return the next combination in lexicographic order, or `Nothing` if there are no further combinations. Starting with the first combination and repeatedly calling this function will iterate through all combinations of a given order.

Return the previous combination in lexicographic order, or `Nothing` if such combination exists.