PermutationStructure

Last edit September 25, 2011

Permutations

Being able to count elements in the set V means the set can be written as {v1, v2, ..., vn}. However, a set may be counted in many different ways.
Various ways to define a permutation
- http://www.cut-the-knot.org/do_you_know/Perm.shtml
There are many ways one can define a permutation, none of which is simple.

Arrays

An analysis of permutations in arrays
- http://hal.archives-ouvertes.fr/docs/00/45/65/58/PDF/main.pdf
In order to analyze this kind of properties, we define an abstract interpretation working on multisets of values, and able to discover invariant equations about such multisets.
Question and Answers
- http://www.velocityreviews.com/forums/t131940-permutations-of-instances-in-array.html

Trees

Permutations as Trees
- http://www.luschny.de/math/factorial/combi/PermutationTrees.html
A permutation tree is a labeled rooted tree that has vertex set {0,1,2,..,n} and root 0, and in which each child is larger than its parent and the children are in ascending order from the left to the right. The power of a permutation tree is the number of descendants of the root. The height of a permutation tree is the number of descendants of the root on the longest chain starting at the root and ending at a leaf. The width of a permutation tree is the number of leafs.
The correspondence with the permutation is given by traversing the periphery of the tree starting at the right hand side of the root and recording a node whenever the node's right edge is passed.