permutation-0.5.0.5: A library for permutations and combinations.

CopyrightCopyright (c) Patrick Perry <patperry@stanford.edu>
LicenseBSD3
MaintainerPatrick Perry <patperry@stanford.edu>
Stabilityexperimental
Safe HaskellNone
LanguageHaskell98

Data.Permute

Contents

Description

Immutable permutations.

Synopsis

Permutations

data Permute #

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

Creating permutations

permute :: Int -> Permute #

Construct an identity permutation of the given size.

listPermute :: Int -> [Int] -> Permute #

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)] -> Permute #

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]] -> Permute #

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 -> Int #

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 :: Permute -> Int -> Int #

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

Permutation properties

size :: Permute -> Int #

Get the size of the permutation.

elems :: Permute -> [Int] #

Get a list of the permutation elements.

isEven :: Permute -> Bool #

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

period :: Permute -> Integer #

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

Permutation functions

inverse :: Permute -> Permute #

Get the inverse of a permutation.

next :: Permute -> Maybe Permute #

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.

prev :: Permute -> Maybe Permute #

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

Applying permutations

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

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)] #

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

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

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

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

cycles p returns the list of disjoin cycles in p.

Sorting

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

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) #

order :: Ord a => Int -> [a] -> Permute #

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] -> Permute #

rank :: Ord a => Int -> [a] -> Permute #

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] -> Permute #