1

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 ?

AlphaBetaGamma96
  • 567
  • 3
  • 6
  • 21
  • 1
    Unrelated, but it's faster to use ```np.sign(vals[:, np.newaxis] - vals)``` instead of ```np.sign(np.expand_dims(vals, -1) - np.expand_dims(vals, -2))``` – Nin17 Aug 27 '22 at 12:21

1 Answers1

1

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
user2357112
  • 260,549
  • 28
  • 431
  • 505
  • But you haven't said anything about the runtime. I think this algorithm is quadratic? If so, then this doesn't answer the question. – A. Kriegman Apr 24 '23 at 16:35
  • @A.Kriegman: It's linear. Every time the inner loop executes an iteration, the number of "out-of-place" elements decreases by at least 1, so the total number of iterations of the inner loop across all iterations of the outer loop is bounded by `len(perm)`. – user2357112 Apr 24 '23 at 23:16