Suppose you have a sequence of unique items, for example:

1, 2, 3, 4, 5

Suppose we have a 'swap' operation whereby you swap any two items in this list. For example, you could get to the following sequences with one swap operation from the start sequence:

2, 1, 3, 4, 5   (swapped 1 and 2)
1, 5, 3, 4, 2   (swapped 2 and 5)
1, 2, 3, 5, 4   (swapped 4 and 5)

If we allow multiple swaps, we find that the set of possible sequences after an even number of swaps is disjoint from the set of possible sequences after an odd number of stops.

Firstly, is there an appropriate terminology when talking about this idea? I can see it's related to group theory but I want a better way of expressing the disjoint between these two sets and the fact we 'jump' between these two sets with each swap.

Secondly, give any permutation of the start sequence, what is the simplest method to determine if it is reached with an even or odd number of swaps?

  • 2
    $\begingroup$ The "swap" operation is called a transposition. The "even" or "odd"-ness of a permutation is called its parity. $\endgroup$ – augurar Aug 24 '14 at 22:36
  • 2
    $\begingroup$ As for computing the parity, see math.stackexchange.com/questions/65923/… $\endgroup$ – augurar Aug 24 '14 at 22:38
  • $\begingroup$ Thanks augurar, that's exactly the sort of references I'm looking for. $\endgroup$ – occulus Aug 25 '14 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.