Identifying swap sequences that produce the same result

I have an associative array where I store key-value pairs, on which I can perform swap operations:

swap(a, b)    // a <-> b
  {
    temp = map.value(b);
    map.value(b) = map.value(a);
    map.value(a) = temp;
  }

Now, given a sequence of swaps, I would like to know if the next swap I perform causes the associative array to go into a state it was previously in:

e.g. the sequences:

1 <-> 2
2 <-> 1

and

1 <-> 2
2 <-> 3
3 <-> 1
2 <-> 3

both do nothing.

I want to be able to detect this by looking at the swap sequence itself. I'm guessing there is a mathematical formulation of problems of this kind, but I cannot seem to figure it out.

I observe that the first example is a loop and the second has a loop, so "detecting loops in a directed graph" might be part of the solution, but I'm not sure how this will fit into the algorithm I am looking for.

The algorithm should also work for unrelated swaps which are interleaved, the simplest example of this being:

1 <-> 2
100 <-> 200
2 <-> 1
200 开发者_如何学Go<-> 100

---

This is an application of permutations (and not really an application of graph theory).

Since these are key-value pairs, where presumably they could be sparse sets of numbers like your last example (1, 2, 100, 200), or even strings:

 Dancer <-> Vixen
 Prancer <-> Blitzen
 Comet <-> Donner
 Vixen <-> Rudolph
 Prancer <-> Dasher
 Comet <-> Cupid
 Vixen <-> Dasher
 Cupid <-> Donner
 Vixen <-> Blitzen
 Prancer <-> Dasher
 Dancer <-> Rudolph
 Prancer <-> Rudolph
 Comet <-> Cupid
 Prancer <-> Vixen

as well as numbers, what I would do is the following (there are at least two ways to do this):

1. Scan the sequence to obtain a list L and a map ML of swap keys, such that L[ML[k]] = k. In the above example, L = [Dancer,Vixen,Prancer,Blitzen,Comet,Donner,Rudolph,Dasher,Cupid] and ML = {Dancer: 0, Vixen: 1, Prancer: 2, Blitzen: 3, Comet: 4, Donner: 5, Rudolph: 6, Dasher: 7, Cupid: 8}

Then either:

A. Procedural solution:

2A. Perform the swaps, in order, on the ML map itself. 3A. To check if the permutation leaves the map intact, verify that ML[L[i]] = i for each integer i between 0 and N-1 where N = the length of L.

B. Matrix solution:

Represent each swap as a permutation matrix, using the list L and map ML to convert from swap keys -> integer indexes. For example, Dancer <-> Vixen swaps elements 0 and 1, which is represented by the permutation matrix:

 010000000
 100000000
 001000000
 000100000
 000010000
 000001000
 000000100
 000000010
 000000001

) and multiply the permutation matrices. Then check if you have the identity matrix at the end.

---

The "A" solution is more efficient but the "B" solution with matrices is more mathematical in nature.