#include "sorting.h"
#include <vector>
#include <numeric>
using namespace std;
int findSwapPairs (int n, int init [], int m, int X[], int Y[], int P[], int Q[]) {
// assume it always ends after exactly n turns
vector<vector<int>> perms (n);
// position perms[i][j] will end up at position j if we don't touch it
perms[n - 1] = vector<int> (n);
iota(perms[n - 1].begin(), perms[n - 1].end(), 0);
for (int i = n - 2; i >= 0; i--) {
perms[i] = perms[i + 1];
swap(perms[i][X[i + 1]], perms[i][Y[i + 1]]);
}
vector<int> cur (init, init + n);
for (int i = 0; i < n; i++) {
swap(cur[X[i]], cur[Y[i]]);
// find a thing that's out of place
int k = -1;
for (int j = 0; j < n; j++) {
if (cur[perms[i][j]] != j) {
k = j;
break;
}
}
if (k == -1) {
P[i] = 0;
Q[i] = 0;
continue;
}
// the value k must be moved to position perms[i][k]
int pk = -1;
for (int j = 0; j < n; j++) {
if (cur[j] == k) {
pk = j;
}
}
P[i] = pk;
Q[i] = perms[i][k];
swap(cur[P[i]], cur[Q[i]]);
}
return n;
}
