No Title Found

AbstractNo Abstract Found

Information entropy

entropy

Equivalence relation

See http://en.wikipedia.org/wiki/Equivalence_relation.

Permutation

[permutation notations, properties]

[equivalence relation, equivalence class, etc.]

1 & 2 & 3 & 4 & 5 & 6
5 & 2 & 1 & 6 & 3 & 4

,

A permutation is a bijection (one-to-one mapping) of a set onto itself.1 For example, consider a set containing six elements. You can think of them as the six colors in a Mastermind game. For convenience, label each element with an index starting from one. A possible permutation is the following:

where the first row displays the elements in the set, and the second row displays the images of the elements under the permutation, i.e. the element that each element is mapped to.

The above notation for the permutation can be abbreviated into one line by only keeping the second row, which becomes \((5 2 1 6 3 4)\).

1 & 2 & 3 & 4 & 5 & 6
5 & 2 & 1 & 6 & 3 & 4

= (1 5 3) (2) (4 6) .

A permutation can be decomposed into a product of disjoint cycles, which partitions the elements of the set into parts where the elements in each part can be permuted independently and then combined to form the complete mapping. For example, the above permutation can be decomposed into the product of three cycles:

It is easy to see that the cycles can be commuted and the elements in a cycle can be rotated without changing the overall permutation. Up to these differences, such decomposition is unique.

1 & 2 & 3 & 4 & 5 & 6
3 & 2 & 5 & 6 & 1 & 4

.

A permutation can be inverted. To find the inverse of a permutation, simply exchange the two roles in the notation and then sort the upper row. In the above example, the inverse permutation is

1 & 2 & 3 & 4 & 5 & 6
* & 2 & * & * & 3 & 4

,

A partial permutation on a set is a bijection between two subsets of it.2 For example, a partial permutation of the above (complete) permutation could be

where the asterisks denote unmapped elements, sometimes known as “holes” of the permutation.

1 & 2 & 3 & 4 & 5 & 6
1 & 2 & 5 & 6 & 3 & 4

.

It is easy to see that any partial permutation can be extended to form a complete permutation. However such extension is not unique. For example, there are \(3! = 6\) ways to extend the above partial permutation, one of which that differs from the original example could be

Graph isomorphism

Below we list several selected strategies for the standard Mastermind game (4 pegs, 6 colors, repetition allowed). These strategies appear in the journal articles of the respective authors. The format is the conventional Irving format.1


  1. Several typos in the original articles have been corrected. In case where the original format is different, it is converted to Irving’s format.