# Module Combinatorial

A collection of common non-deterministic and/or combinatorial operations. Many operations are intended to operate on sets. The representation of these sets is not hidden; rather sets are represented as lists. Ideally these lists contains no duplicate elements and the order of their elements cannot be observed. In practice, these conditions are not enforced.

Author: Sergio Antoy (with extensions by Michael Hanus)

Version: April 2016

## Summary of exported operations:

 ```permute :: [a] -> [a]```    Compute any permutation of a list. ```subset :: [a] -> [a]```    Compute any sublist of a list. ```allSubsets :: [a] -> [[a]]```    Compute all the sublists of a list. ```splitSet :: [a] -> ([a],[a])```    Split a list into any two sublists. ```sizedSubset :: Int -> [a] -> [a]```    Compute any sublist of fixed length of a list. ```partition :: [a] -> [[a]]```    Compute any partition of a list.

## Exported operations:

 ```permute :: [a] -> [a]```    Compute any permutation of a list. Example call: `(permute xs)` Parameters: `xs` : The list. Returns: A permutation of the argument. Properties: `permute [1,2,3,4] ~> [1,3,4,2]` (permute1234) `length (permute xs) <~> length xs` (permLength) `anyOf (permute xs) <~> anyOf xs` (permElems) Further infos: solution complete, i.e., able to compute all solutions
 ```subset :: [a] -> [a]```    Compute any sublist of a list. The sublist contains some of the elements of the list in the same order. Example call: `(subset xs)` Parameters: `xs` : The list. Returns: A sublist of the argument. Properties: `subset [1,2,3,4] ~> [1,3]` (subset1234) ```subset [1,2,3] <~> ([1,2,3] ? ([1,2] ? ([1,3] ? ( ? ([2,3] ? ( ? ( ? [])))))))``` (subset123) `anyOf (subset xs) <~ anyOf xs` (subsetElems) Further infos: solution complete, i.e., able to compute all solutions
 ```allSubsets :: [a] -> [[a]]```    Compute all the sublists of a list. Example call: `(allSubsets xs)` Parameters: `xs` : The list. Returns: All the sublists of the argument. Properties: `allSubsets [1,2,3] -=- [[],,[1,2],[1,2,3],[1,3],,[2,3],]` (allSubsets123)
 ```splitSet :: [a] -> ([a],[a])```    Split a list into any two sublists. Example call: `(splitSet xs)` Parameters: `xs` : The list. Returns: A pair consisting of two complementary sublists of the argument. Properties: `splitSet [1,2,3,4] ~> ([1,3,4],)` (splitSet1234) `(\(xs,ys) -> length xs + length ys) (splitSet xs) <~> length xs` (splitSetLengths) `(\(xs,ys) -> anyOf xs ? anyOf ys) (splitSet xs) <~> anyOf xs` (splitSetElems) Further infos: solution complete, i.e., able to compute all solutions
 ```sizedSubset :: Int -> [a] -> [a]```    Compute any sublist of fixed length of a list. Similar to `subset`, but the length of the result is fixed. Example call: `(sizedSubset c xs)` Parameters: `c` : The length of the output sublist. `xs` : The input list. Returns: A sublist of `xs` of length `c`. Precondition: `(sizedSubset c _)` requires ``` c >= 0``` (sizedSubset'pre) Properties: `((c >= 0) && (length xs >= c)) ==> (length (sizedSubset c xs) <~> c)` (sizedSubsetLength) `((c >= 0) && (length xs < c)) ==> failing (sizedSubset c xs)` (sizedSubsetLengthTooSmall)
 ```partition :: [a] -> [[a]]```    Compute any partition of a list. The output is a list of non-empty lists such that their concatenation is a permutation of the input list. No guarantee is made on the order of the arguments in the output. Example call: `(partition xs)` Parameters: `xs` : The input list. Returns: A partition of `xs` represented as a list of lists. Properties: `partition [1,2,3,4] ~> [,[2,3],]` (partition1234) ```partition [1,2,3] <~> ([[1,2,3]] ? ([[2,3],] ? ([[1,3],] ? ([,[1,2]] ? [,,]))))``` (partition123) `sum (map length (partition xs)) <~> length xs` (partitionLengths) `anyOf (map anyOf (partition xs)) <~> anyOf xs` (partitionElems) Further infos: solution complete, i.e., able to compute all solutions