Stability | experimental |
---|---|
Maintainer | Patrick Perry <patperry@stanford.edu> |
Safe Haskell | None |
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] -> PermuteSource
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)] -> 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 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
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 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] -> 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 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
.