Permutation Structure

Permutations

• http://www.cut-the-knot.org/do_you_know/permutation.shtml

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.

See also MatroidTheory

Project WikiBatics GoogleThis