|
If a permutation were assigned to each inversion set using the element-based definition, the resulting order of permutations would be that of a [[Cayley graph]], where an edge corresponds to the swapping of two elements on consecutive places. This Cayley graph of the symmetric group is similar to its permutohedron, but with each permutation replaced by its inverse.
==In computer science==
In computer science, it may be useful to calculate the total number of inversions of a permutation. A way to do it is by using a modified version of the [[merge sort]] algorithm. For example, using a modified version of its [[Merge_sort#Top-down_implementation|top-down recursive implementation]]:
<source lang="C">
// Array A[] has the items to sort; array B[] is a work array.
TopDownMergeSort(A[], B[], n)
{
int inversions;
CopyArray(A, 0, n, B); // duplicate array A[] into B[]
inversions=TopDownSplitMerge(B, 0, n, A); // sort data from B[] into A[]
printf("The total number of inversions is: %d\n", inversions);
}
// Sort the given run of array A[] using array B[] as a source.
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
int TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
int inversions=0;
if(iEnd - iBegin < 2) // if run size == 1
return; // consider it sorted
// split the run longer than 1 item into halves
iMiddle = (iEnd + iBegin) / 2; // iMiddle = mid point
// recursively sort both runs from array A[] into B[]
inversions+=TopDownSplitMerge(A, iBegin, iMiddle, B); // sort the left run
inversions+=TopDownSplitMerge(A, iMiddle, iEnd, B); // sort the right run
// merge the resulting runs from array B[] into A[]
inversions+=TopDownMerge(B, iBegin, iMiddle, iEnd, A);
return inversions;
}
// Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1 ].
// Result is B[ iBegin:iEnd-1 ].
int TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
i = iBegin, j = iMiddle;
// While there are elements in the left or right runs...
for (k = iBegin; k < iEnd; k++) {
// If left run head exists and is <= existing right run head.
if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
B[k] = A[i];
i = i + 1;
} else {
inversions++;
B[k] = A[j];
j = j + 1;
}
}
return inversions;
}
CopyArray(A[], iBegin, iEnd, B[])
{
for(k = iBegin; k < iEnd; k++)
B[k] = A[k];
}
</source>
== See also ==
| 