Data.Permute

Immutable permutations.

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

Eq Permute

Show Permute

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.

unsafeAt :: Permute -> Int -> Int

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