Copyright | Copyright (c) Patrick Perry <patperry@stanford.edu> |
---|---|
License | BSD3 |
Maintainer | Patrick Perry <patperry@stanford.edu> |
Stability | experimental |
Safe Haskell | None |
Language | Haskell98 |
Data.Permute
Contents
Description
Immutable permutations.
- data Permute
- permute :: Int -> Permute
- listPermute :: Int -> [Int] -> Permute
- swapsPermute :: Int -> [(Int, Int)] -> Permute
- cyclesPermute :: Int -> [[Int]] -> Permute
- at :: Permute -> Int -> Int
- unsafeAt :: Permute -> Int -> Int
- indexOf :: Permute -> Int -> Int
- size :: Permute -> Int
- elems :: Permute -> [Int]
- isEven :: Permute -> Bool
- period :: Permute -> Integer
- inverse :: Permute -> Permute
- next :: Permute -> Maybe Permute
- prev :: Permute -> Maybe Permute
- swaps :: Permute -> [(Int, Int)]
- invSwaps :: Permute -> [(Int, Int)]
- cycleFrom :: Permute -> Int -> [Int]
- cycles :: Permute -> [[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
Int
s. The permutation represents a reordering of
the integers 0, ..., (n-1)
. The permutation sents the value p[i] to
i
.
Creating permutations
listPermute :: Int -> [Int] -> Permute Source #
Construct a permutation from a list of elements.
listPermute n is
creates a permutation of size n
with
the i
th 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 i
th element of the permutation
p
. The index i
must be in the range 0..(n-1)
, where n
is the
size of the permutation.
Permutation properties
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
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
.
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] -> 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
.
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 i
th element of xs
.
The results are undefined if n
is greater than the length of xs
.
This is a special case of rankBy
.