| Stability | experimental |
|---|---|
| Maintainer | Patrick Perry <[email protected]> |
Data.Permute
Contents
Description
Immutable permutations.
- data Permute
- permute :: Int -> Permute
- listPermute :: Int -> [Int] -> Permute
- swapsPermute :: Int -> [(Int, Int)] -> Permute
- apply :: Permute -> Int -> Int
- unsafeApply :: Permute -> Int -> Int
- size :: Permute -> Int
- elems :: Permute -> [Int]
- inverse :: Permute -> Permute
- next :: Permute -> Maybe Permute
- prev :: Permute -> Maybe Permute
- swaps :: Permute -> [(Int, Int)]
- invSwaps :: Permute -> [(Int, Int)]
- sort :: Ord a => Int -> [a] -> ([a], Permute)
- sortBy :: (a -> a -> Ordering) -> Int -> [a] -> ([a], Permute)
- order :: Ord a => Int -> [a] -> Permute
- orderBy :: (a -> a -> Ordering) -> Int -> [a] -> Permute
- rank :: Ord a => Int -> [a] -> Permute
- rankBy :: (a -> a -> Ordering) -> Int -> [a] -> Permute
Permutations
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 ith element of the array stores
the value p[i].
Creating permutations
listPermute :: Int -> [Int] -> PermuteSource
Construct a permutation from a list of elements.
listPermute n is creates a permuation 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 permuation 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.
Accessing permutation elements
apply :: Permute -> Int -> IntSource
apply 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.
unsafeApply :: Permute -> Int -> IntSource
Permutation properties
Permutation functions
next :: Permute -> Maybe PermuteSource
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 PermuteSource
Return the previous permutation in lexicographic order, or Nothing
if there is no such permutation.
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.
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.
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.
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.