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 ith element of the array stores the value p[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 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)] -> Permute

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 -> Int

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 -> Int

Permutation properties

size :: Permute -> Int

Get the size of the permutation.

elems :: Permute -> [Int]

Get a list of the permutation elements.

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 there is no such permutation.

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.

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