permutation-0.4.1: A library for permutations and combinations.

Stability experimental Patrick Perry

Data.Permute

Description

Immutable permutations.

Synopsis

# Permutations

data Permute Source

The immutable permutation data type. Internally, a permutation of size n is stored as an 0-based array of n Ints. The permutation represents a reordering of the integers 0, ..., (n-1). The permutation sents the value p[i] to i.

Instances

 Eq Permute Show Permute

# Creating permutations

Construct an identity permutation of the given size.

listPermute :: Int -> [Int] -> PermuteSource

Construct a permutation from a list of elements. listPermute n is creates a permutation of size n with the ith element equal to is !! i. For the permutation to be valid, the list is must have length n and contain the indices 0..(n-1) exactly once each.

swapsPermute :: Int -> [(Int, Int)] -> PermuteSource

Construct a permutation from a list of swaps. swapsPermute n ss creats a permutation of size n given by a sequence of swaps. If ss is [(i0,j0), (i1,j1), ..., (ik,jk)], the sequence of swaps is i0 <-> j0, then i1 <-> j1, and so on until ik <-> jk.

cyclesPermute :: Int -> [[Int]] -> PermuteSource

Construct a permutation from a list of disjoint cycles. cyclesPermute n cs creates a permutation of size n which is the composition of the cycles cs.

# Accessing permutation elements

at :: Permute -> Int -> IntSource

at p i gets the value of the ith element of the permutation p. The index i must be in the range 0..(n-1), where n is the size of the permutation.

indexOf p x gets an index i such that at p i equals x.

# Permutation properties

Get the size of the permutation.

elems :: Permute -> [Int]Source

Get a list of the permutation elements.

Whether or not the permutation is made from an even number of swaps

period p - The first power of p that is the identity permutation

# Permutation functions

Get the inverse of a permutation.

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

Return the previous permutation in lexicographic order, or Nothing if no such permutation exists.

# Applying permutations

swaps :: Permute -> [(Int, Int)]Source

Get a list of swaps equivalent to the permutation. A result of [ (i0,j0), (i1,j1), ..., (ik,jk) ] means swap i0 <-> j0, then i1 <-> j1, and so on until ik <-> jk.

invSwaps :: Permute -> [(Int, Int)]Source

Get a list of swaps equivalent to the inverse of permutation.

cycleFrom :: Permute -> Int -> [Int]Source

cycleFrom p i gets the list of elements reachable from i by repeated application of p.

cycles :: Permute -> [[Int]]Source

cycles p returns the list of disjoin cycles in p.

# Sorting

sort :: Ord a => Int -> [a] -> ([a], Permute)Source

sort n xs sorts the first n elements of xs and returns a permutation which transforms xs into sorted order. The results are undefined if n is greater than the length of xs. This is a special case of sortBy.

sortBy :: (a -> a -> Ordering) -> Int -> [a] -> ([a], Permute)Source

order :: Ord a => Int -> [a] -> PermuteSource

order n xs returns a permutation which rearranges the first n elements of xs into ascending order. The results are undefined if n is greater than the length of xs. This is a special case of orderBy.

orderBy :: (a -> a -> Ordering) -> Int -> [a] -> PermuteSource

rank :: Ord a => Int -> [a] -> PermuteSource

rank n xs eturns a permutation, the inverse of which rearranges the first n elements of xs into ascending order. The returned permutation, p, has the property that p[i] is the rank of the ith element of xs. The results are undefined if n is greater than the length of xs. This is a special case of rankBy.

rankBy :: (a -> a -> Ordering) -> Int -> [a] -> PermuteSource