OAlg.Entity.Sequence.Permutation

permutations on totally ordered index types i to permute the items of sequences.

Permutation

data Permutation i

permutation of a totally ordered index type i which yield a bijection pmt on i. They are constructed using

• make of a valid PermutationForm, which defines also the validity for the constructed permutation.
• swap and the Multiplicative structure for permutations.
• permuteBy for PermutableSequence.
• xPermutation to generate randomly permutations.

In the following the total right operation <* of a permutation on several types of sequences will be defined to achieve the permutation of there items.

Definitions

List

Let xs be in [x] with ConstructableSequence [] r [x] and p a permutation in Permutation r, then xs <* p is given by sqcIndexMap is (pmt p) xs, where is is the image of the support of xs under the inverse of p.

CSequence

Let xs be in CSequence x with ConstructableSequence CSequence N x and p a permutation in Permutation N, then xs <* p is given by sqcIndexMap is (pmt p) xs, where is is the image of the support of xs under the inverse of p.

PSequence

Let xs be in PSequence i x with ConstructableSequence (PSequence i) i x and p a permutation in Permutation i, then xs <* p is given by sqcIndexMap is (pmt p) xs, where is is the image of the support of xs under the inverse of p.

Permutation

Let xs, p be in Permutation i, then xs <* p is given by *.

Note The given definitions are not very efficient and only terminate for finite sequences (in fact, a more efficient implementation has been chosen that also terminates for infinite sequences (see example below)). However, they serve on the one hand to define the semantic and to 'prove' the properties for TotalOpr and on the other hand to verify the chosen implementation for finite sequences (see prpOprPermutation).

Examples

>>> "abcdef" <* (swap 2 5 :: Permutation N)
"abfdec"

the support of a sequence and the relevant image of a permutation may be disjoint which will leave the sequence untouched

>>> "abcdef" <* (swap 7 10 :: Permutation N)
"abcdef"

the intersection of the support of a sequence with the relevant image of a permutation may be a non empty proper sub set

>>> "abcdef" <* swap 2 10 :: Permutation N)
"abdefc"

the result can be interpreted as: first, put c at position 10 and Nothing (which is the item at position 10) at position 2. Second, strip all nothings form it.

Although the given definition of the permutation of sequences dose not terminate for infinite sequences, its implementation will terminate

>>> takeN 5 $ (([0..] :: [N]) <* (swap 1 2 :: Permutation N)
[0,2,1,3,4]

Instances

Ord i => Sequence Permutation i i

Defined in OAlg.Entity.Sequence.Permutation

Methods

graph :: p i -> Permutation i -> Graph i i

list :: p i -> Permutation i -> [(i, i)]

(??) :: Permutation i -> i -> Maybe i

(Entity i, Ord i) => PermutableSequence Permutation i i

Defined in OAlg.Entity.Sequence.Permutation

Methods

permuteBy :: p i -> (w -> w -> Ordering) -> (i -> w) -> Permutation i -> (Permutation i, Permutation i)

Show i => Show (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

Methods

showsPrec :: Int -> Permutation i -> ShowS

show :: Permutation i -> String

showList :: [Permutation i] -> ShowS

Eq i => Eq (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

Methods

(==) :: Permutation i -> Permutation i -> Bool

(/=) :: Permutation i -> Permutation i -> Bool

Eq i => Constructable (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

Methods

make :: Form (Permutation i) -> Permutation i

Exposable (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

Associated Types

type Form (Permutation i)

Methods

form :: Permutation i -> Form (Permutation i)

LengthN (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

Methods

lengthN :: Permutation i -> N

(Entity i, Ord i) => Validable (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

Methods

valid :: Permutation i -> Statement

(Entity i, Ord i) => Entity (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

(Entity i, Ord i) => Exponential (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

Associated Types

type Exponent (Permutation i)

Methods

(^) :: Permutation i -> Exponent (Permutation i) -> Permutation i

(Entity i, Ord i) => Cayleyan (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

(Entity i, Ord i) => Invertible (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

Methods

tryToInvert :: Permutation i -> Solver (Permutation i)

invert :: Permutation i -> Permutation i

isInvertible :: Permutation i -> Bool

zpower :: Permutation i -> Z -> Permutation i

(Entity i, Ord i) => Multiplicative (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

Methods

one :: Point (Permutation i) -> Permutation i

(*) :: Permutation i -> Permutation i -> Permutation i

npower :: Permutation i -> N -> Permutation i

(Entity i, Ord i) => Oriented (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

Associated Types

type Point (Permutation i)

Methods

orientation :: Permutation i -> Orientation (Point (Permutation i))

start :: Permutation i -> Point (Permutation i)

end :: Permutation i -> Point (Permutation i)

Total (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

Entity x => Opr (Permutation N) (CSequence x)

Defined in OAlg.Entity.Sequence.Permutation

Methods

(<*) :: CSequence x -> Permutation N -> CSequence x

Opr (Permutation N) [x]

Defined in OAlg.Entity.Sequence.Permutation

Methods

(<*) :: [x] -> Permutation N -> [x]

(Entity i, Ord i) => Opr (Permutation i) (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

Methods

(<*) :: Permutation i -> Permutation i -> Permutation i

Entity x => TotalOpr (Permutation N) (CSequence x)

Defined in OAlg.Entity.Sequence.Permutation

Entity x => TotalOpr (Permutation N) [x]

Defined in OAlg.Entity.Sequence.Permutation

(Entity i, Ord i) => TotalOpr (Permutation i) (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

Entity p => Opr (Permutation N) (Dim x p)

Defined in OAlg.Entity.Matrix.Dim

Methods

(<*) :: Dim x p -> Permutation N -> Dim x p

Ord i => Opr (Permutation i) (Col i x)

Defined in OAlg.Entity.Matrix.Entries

Methods

(<*) :: Col i x -> Permutation i -> Col i x

Ord i => Opr (Permutation i) (PSequence i x)

Defined in OAlg.Entity.Sequence.Permutation

Methods

(<*) :: PSequence i x -> Permutation i -> PSequence i x

Ord j => Opr (Permutation j) (Row j x)

Defined in OAlg.Entity.Matrix.Entries

Methods

(<*) :: Row j x -> Permutation j -> Row j x

(Oriented x, Entity p) => TotalOpr (Permutation N) (Dim x p)

Defined in OAlg.Entity.Matrix.Dim

(Entity x, Entity i, Ord i) => TotalOpr (Permutation i) (Col i x)

Defined in OAlg.Entity.Matrix.Entries

(Entity i, Ord i, Entity x) => TotalOpr (Permutation i) (PSequence i x)

Defined in OAlg.Entity.Sequence.Permutation

(Entity x, Entity j, Ord j) => TotalOpr (Permutation j) (Row j x)

Defined in OAlg.Entity.Matrix.Entries

type Form (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

type Form (Permutation i) = PermutationForm i

type Exponent (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

type Exponent (Permutation i) = Z

type Point (Permutation i)

Defined in OAlg.Entity.Sequence.Permutation

type Point (Permutation i) = ()

pmt :: Ord i => Permutation i -> i -> i

the bijection on i for a given permutation and is defined via restrict pmf.

swap :: (Entity i, Ord i) => i -> i -> Permutation i

swapping.

Property Let p = swap n (i,j), then holds: If i,j < n then p is the permutation given by swapping i with j, otherwise a exception will be thrown.

Permutable

class (Sequence s i x, TotalOpr (Permutation i) (s x)) => PermutableSequence s i x where

total right operations of permutations on sequences, admitting the following properties:

Property Let s, i, x be an instance of PermutableSequence s i x, then holds:

1. Let xs be in s x, p in Permutation i with image z p <<= support z xs for some z in z i, then holds: (xs <* p) ?? i == ((xs ??) . pmt p) i for all i in support z xs.

2. Let xs be in s x, w in x -> w, c in w -> w -> Ordering and z in z i, then holds: Let (xs',p) = permuteBy z c w xs in

   1. xs' == xs <* p.
   2. xs' is ordered according to c by applying w to its items.
   3. image z p <<= support z xs.

Examples

>>> fst $ permuteBy nProxy compare isUpper "abCd1eFgH"
"abd1egCFH"

as False < True

>>> fst $ permuteBy nProxy (coCompare compare) isUpper "abCd1eFgH"
"CFHabd1eg"

which orders it in the reverse ordering.

Methods

permuteBy :: p i -> (w -> w -> Ordering) -> (x -> w) -> s x -> (s x, Permutation i)

a resulting permuation.

Instances

Entity x => PermutableSequence CSequence N x

Defined in OAlg.Entity.Sequence.Permutation

Methods

permuteBy :: p N -> (w -> w -> Ordering) -> (x -> w) -> CSequence x -> (CSequence x, Permutation N)

(Entity i, Ord i) => PermutableSequence Permutation i i

Defined in OAlg.Entity.Sequence.Permutation

Methods

permuteBy :: p i -> (w -> w -> Ordering) -> (i -> w) -> Permutation i -> (Permutation i, Permutation i)

Entity x => PermutableSequence [] N x

Defined in OAlg.Entity.Sequence.Permutation

Methods

permuteBy :: p N -> (w -> w -> Ordering) -> (x -> w) -> [x] -> ([x], Permutation N)

(Oriented x, Entity p) => PermutableSequence (Dim x) N p

Defined in OAlg.Entity.Matrix.Dim

Methods

permuteBy :: p0 N -> (w -> w -> Ordering) -> (p -> w) -> Dim x p -> (Dim x p, Permutation N)

(Entity x, Entity i, Ord i) => PermutableSequence (Col i) i x

Defined in OAlg.Entity.Matrix.Entries

Methods

permuteBy :: p i -> (w -> w -> Ordering) -> (x -> w) -> Col i x -> (Col i x, Permutation i)

(Entity x, Entity j, Ord j) => PermutableSequence (Row j) j x

Defined in OAlg.Entity.Matrix.Entries

Methods

permuteBy :: p j -> (w -> w -> Ordering) -> (x -> w) -> Row j x -> (Row j x, Permutation j)

(Entity x, Entity i, Ord i) => PermutableSequence (PSequence i) i x

Defined in OAlg.Entity.Sequence.Permutation

Methods

permuteBy :: p i -> (w -> w -> Ordering) -> (x -> w) -> PSequence i x -> (PSequence i x, Permutation i)

permuteByN :: PermutableSequence s N x => (w -> w -> Ordering) -> (x -> w) -> s x -> (s x, Permutation N)

orders the permutable sequence according to the given ordering an delivers the resulting permutation form.

Form

newtype PermutationForm i

form of a permutation from i to i which is given by pmf.

Property Let p = PermutationForm jis be in PermutationForm i, then holds: support z p == image z p for some proxy z in z i.

The partial sequence ijs is called the relevant part of p.

Constructors

PermutationForm (PSequence i i)

Instances

Ord i => Sequence PermutationForm i i

Defined in OAlg.Entity.Sequence.Permutation

Methods

graph :: p i -> PermutationForm i -> Graph i i

list :: p i -> PermutationForm i -> [(i, i)]

(??) :: PermutationForm i -> i -> Maybe i

Show i => Show (PermutationForm i)

Defined in OAlg.Entity.Sequence.Permutation

Methods

showsPrec :: Int -> PermutationForm i -> ShowS

show :: PermutationForm i -> String

showList :: [PermutationForm i] -> ShowS

Eq i => Eq (PermutationForm i)

Defined in OAlg.Entity.Sequence.Permutation

Methods

(==) :: PermutationForm i -> PermutationForm i -> Bool

(/=) :: PermutationForm i -> PermutationForm i -> Bool

LengthN (PermutationForm i)

Defined in OAlg.Entity.Sequence.Permutation

Methods

lengthN :: PermutationForm i -> N

Eq i => Reducible (PermutationForm i)

Defined in OAlg.Entity.Sequence.Permutation

Methods

reduce :: PermutationForm i -> PermutationForm i

(Entity i, Ord i) => Validable (PermutationForm i)

Defined in OAlg.Entity.Sequence.Permutation

Methods

valid :: PermutationForm i -> Statement

(Entity i, Ord i) => Entity (PermutationForm i)

Defined in OAlg.Entity.Sequence.Permutation

(Entity i, Ord i) => Oriented (PermutationForm i)

Defined in OAlg.Entity.Sequence.Permutation

Associated Types

type Point (PermutationForm i)

Methods

orientation :: PermutationForm i -> Orientation (Point (PermutationForm i))

start :: PermutationForm i -> Point (PermutationForm i)

end :: PermutationForm i -> Point (PermutationForm i)

type Point (PermutationForm i)

Defined in OAlg.Entity.Sequence.Permutation

type Point (PermutationForm i) = ()

pmf :: Ord i => PermutationForm i -> i -> i

the associated function i to i and is given by:

Definition Let p = PermutationForm jis be in PermutationForm i then pmf p i is defined by: If there exists an (j,i') in psqxs jis with i' == i then pmf p i = j else pmf p i = i.

Note

1. If the partial sequence ijs is valid, then for all i in i there exists at most one (_,i') in psqxs jis such that i' == i. As such, the function pmf p is well defined.
2. If the permutation form p itself is valid than pmf p is a bijection and as such a permutation of i.
3. The behavior of pmf differs from ?? as its evaluation will not end up in a IndexOutOfSupport-exception.

X

xPermutation

Arguments

:: (Entity i, Ord i)

=> N

maximal number of swappings.

-> X i

span of the swappings.

-> X (Permutation i)

random variable of permutations.

xPermutationB :: (Ord i, Enum i) => i -> i -> X (Permutation i)

random variable of permutations within the given bounds.

xPermutationN :: N -> X (Permutation N)

random variable of permutations of the index set [0..prd n].

xMltPermutation :: (Entity i, Ord i) => N -> X i -> XMlt (Permutation i)

random variable for validating the Multiplicative structure.

Propositions

prpPermutation :: Statement

validity of the functionality of the module Permutation.

prpPermutableSequence :: (PermutableSequence s i x, Entity x, Entity i, Show w) => N -> z i -> (w -> w -> Ordering) -> (x -> w) -> X (s x) -> Statement

validity for PermutableSequence.

prpOprPermutation :: Statement

validity of the total right operation <* of permutations on sequences.