Sym.Perm

Generating permutations: rank and unrank

Documentation

module Sym.Internal.CLongArray

type Perm = CLongArray

A permutation is just a CLongArray. By convention a permutation of size n is understood to be a permutation of [0..n-1].

emptyperm :: Perm

The unique permutation length zero.

one :: Perm

The unique permutation length one.

idperm :: Int -> Perm

The identity permutation.

ebb :: Int -> Perm

The reverse of the identity permutation.

mkPerm :: Ord a => [a] -> Perm

Construct a permutation from a list of elements. As opposed to fromList this is a safe function in the sense that the output of mkPerm xs is guaranteed to be a permutation of [0..length xs-1]. E.g., mkPerm "baxa" == fromList [2,0,3,1].

rank :: Perm -> Integer

The rank of the given permutation, where the rank is defined as in [W. Myrvold and F. Ruskey, Ranking and Unranking Permutations in Linear Time, Information Processing Letters, 79 (2001) 281-284].

unrank :: Int -> Integer -> Perm

The permutation of size n whose rank is r, where the rank is defined as in [W. Myrvold and F. Ruskey, Ranking and Unranking Permutations in Linear Time, Information Processing Letters, 79 (2001) 281-284].

perms :: Int -> [Perm]

All permutations of a given size.