I wrote this trying to find the best way to sort a list, only swapping two elements at a time. Turns out I developed a basic theory of permutations with unweildy notation. Lists are permutations, swaps are transpositions, and loops are cycles.
A list of length is defined as any bijective function where . A swap on a list at two indices denoted results in another list defined by
Since a list is bijective, any swap on a list results in a bijection and is a list. The unique identity list of length is denoted as and is defined as .
The loop of a list at index denoted is defined as the sequence where
Every loop is periodic.
For a given loop of a list of length , if , then since is well defined, . Since is bijective, it is also true that if , then . Suppose there does not exist a where . Then there does not exist a where . Continuing by induction, the loop must have no repeating values. But every value of the infinite loop must be one from the finite set , which is a contradiction. Thus such a exists, and the loop is periodic.
Let be the smallest such , and define the length of a loop to be .
Two loops and are considered equivalent if there exists an where for all . This relation is an equivalence relation, so it can be denoted .
For any index , the .
This follows from and .
if and only if .
Since , then for some . Then can be applied times.
If , then where .
This follows from .
For a given list , if and , then results in a list with exactly more unique loops than in .
Let . By , the number of loops not containing or are the same in both and .
Let be the first index in where . Then for , , but
This indicates that while . Therefore by , and has one more loop than has.
For a given list , if and , then results in a list with exactly fewer unique loops than in .
Note that where because of and . Then for , and . Thus , and by , . showed that must contain more unique loops than .
and together state that a swap on different indices only increases or decreases the number of loops by .
A list of length has unique loops if and only if it is .
Since a list of length cannot have more than loops, contains the maximum number of loops.
A list has a loop with length greater than if and only if it is not .
The method of finding and performing will always increase the number of loops by until is reached in the fewest possible swaps.