I was just wondering if there's a way to compute the sign of a permutation within linear (or at least better than n^2?) time

For example, let's say I have an array of n numbers and I permute two elements within this array which would flip the sign of the permutation. I have a function that can compute this in n^2 time, however, it seems there might be a more efficient algorithm.

I've attached a minimal reproducible example of computing in quadratic time,

import numpy as np

vals = np.arange(1,6,1)
pvals = np.arange(1,6,1)
pvals[0], pvals[1] = pvals[1], pvals[0] #swap

def quadratic(vals):
  sgn_matrix = np.sign(np.expand_dims(vals, -1) - np.expand_dims(vals, -2))
  return np.prod(np.tril(np.ones_like(sgn_matrix))   np.triu(sgn_matrix, 1))

def sub_quadratic(vals):
  #algorithm quicker than quadratic time?

sgn = quadratic(vals)
print(sgn)   #prints  1 

psgn = quadratic(pvals)
print(psgn)  #prints -1 (because one permutation)

I have had a look around SO (here for example) and people keep talking about cyclic permutations which apparently can compute in linear time but it's something I'm unaware of completely and can't find much of myself.

TL;DR Does anyone know of a method for computing the sign of a permutation in sub-quadratic time ?

CodePudding user response：

Just decompose it into transpositions and check whether you needed an even or odd number of transpositions:

def permutation_sign(perm):
    parity = 1
    perm = perm.copy()
    for i in range(len(perm)):
        while perm[i] != i 1:
            parity *= -1
            j = perm[i] - 1
            # Note: if you try to inline the j computation into the next line,
            # you'll get evaluation order bugs.
            perm[i], perm[j] = perm[j], perm[i]
    return parity