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 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 Source # 
Instance details

Defined in Data.Permute.Base

Methods

(==) :: Permute -> Permute -> Bool #

(/=) :: Permute -> Permute -> Bool #

Show Permute Source # 
Instance details

Defined in Data.Permute.Base

Creating permutations

permute :: Int -> Permute Source #

Construct an identity permutation of the given size.

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

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

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

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

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

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

Permutation properties

size :: Permute -> Int Source #

Get the size of the permutation.

elems :: Permute -> [Int] Source #

Get a list of the permutation elements.

isEven :: Permute -> Bool Source #

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

period :: Permute -> Integer Source #

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

Permutation functions

inverse :: Permute -> Permute Source #

Get the inverse of a permutation.

next :: Permute -> Maybe Permute Source #

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

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

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

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

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