9 February 2023

An interesting method of computing permutation parity using the 3-cycle composition property:

bool parity(int * p, int n) {
    if (n == 1) return 0;
    int C[n], I[n];
    for(int i = 0; i < n; i++)
        C[i] = i, I[i] = i;
    for (int i = 0; i < n - 2; i++) {
        if (C[i] != p[i]) {
            int j = I[p[i]];
            int tmp = C[i];
            C[i] = C[j];
            int k = j == n - 1;
            C[j] = C[n - 1 - k];
            C[n - 1 - k] = tmp;
            I[C[n - 1 - k]] = n - 1 - k;
            I[C[j]] = j;
            I[C[i]] = i;
        }
    }
    return C[n - 1] != p[n - 1];
}

Unsurprisingly, translates horribly into array logic languages. I wonder how would I implement it in my Lisp…