CODEWITHSUNDEEP
algorithm
Wirawan Purwanto
Wirawan Purwanto

Reputation: 4043

A simple code to detect the permutation sign

supposed I have an array of integers:

1 2 5 3 7 6

What is a simple enough algorithm that determines if this is an even or odd permutation of the numbers in sorted fashion (i.e. 1 2 3 5 6 7)? Performance is not terribly important here; I'd rather have a simple code.

Upvotes: 3

Views: 3911

Answers (9)

卞舒言
卞舒言

Reputation: 31

Here is an O(n) answer.

(define (sign-of-permutation permutation)
  (define p (vector-copy permutation))
  (define l (vector-length p))
  (define q (make-vector l))
  (let iter ((i 0))
    (unless (= i l)
      (define x (vector-ref p i))
      (vector-set! q x i)
      (iter (+ i 1))))
  (printf "~s\n" p)
  (let iter ((i 0) (s 1))
    (if (= i l)
        s
        (let ((x (vector-ref p i)))
          (if (= i x)
              (iter (+ i 1) s)
              (let ((j (vector-ref q i)))
                (vector-swap! p i j)
                (printf "~s\n" p)
                (vector-swap! q x i)
                (iter (+ i 1) (- s))))))))

Here is an example.

> (define p (vector 3 4 2 0 1))
> (sign-of-permutation p)
#(3 4 2 0 1)
#(0 4 2 3 1)
#(0 1 2 3 4)
1

Upvotes: 1

Codeman
Codeman

Reputation: 157

See how Sympy does it. In a nutshell, here is how it works:

You can find the number of cycles, subtract it from the length of the array, take its parity, and then find the sign. Finding the number of cycles is O(N) by using a set or a boolean array to check visited values. All the other operations are O(1), so all in all, this new approach is O(N).

Upvotes: 1

Christopher Larsen
Christopher Larsen

Reputation: 1411

Simple and done in python for when I inevitably need to find this again: 

def is_even(p):

    if len(p) == 1:
        return True

    trans = 0

    for i in range(0,len(p)):
        j = i + 1

        for j in range(j, len(p)):
            if p[i] > p[j]: 
                trans = trans + 1

    return ((trans % 2) == 0)

Upvotes: 1

user2376234
user2376234

Reputation:

Another simple code that runs in O(nlogn), and tr[] is an array with all 0s in it initially.

int ans=0;
for(int i=1;i<=n;i++)
{
    for(int j=a[i];j;j-=j&-j) ans+=tr[j];
    for(int j=a[i];j<=n;j+=j&-j) tr[j]++;
}
printf((n*(n-1)/2-ans)%2?"odd\n":"even");

Upvotes: 1

Francesco De Lisi
Francesco De Lisi

Reputation: 1523

Try to implement your own version of Heap Sort Algorithm having a complexity of O(n log n) and counting the number of permutation in order to build your signature (I assume you know what I'm talking about).

Sample code:

public static void HeapSort(int[] input)
{
    //Build-Max-Heap
    int heapSize = input.Length;
    for (int p = (heapSize - 1) / 2; p >= 0; p--)
        MaxHeapify(input, heapSize, p);

    for (int i = input.Length - 1; i > 0; i--)
    {
        //Swap
        int temp = input[i];
        input[i] = input[0];
        input[0] = temp;

        heapSize--;
        MaxHeapify(input, heapSize, 0);
    }
}

private static void MaxHeapify(int[] input, int heapSize, int index)
{
    int left = (index + 1) * 2 - 1;
    int right = (index + 1) * 2;
    int largest = 0;

    if (left < heapSize && input[left] > input[index])
        largest = left;
    else
        largest = index;

    if (right < heapSize && input[right] > input[largest])
        largest = right;

    if (largest != index)
    {
        int temp = input[index];
        input[index] = input[largest];
        input[largest] = temp;

        MaxHeapify(input, heapSize, largest);
    }
}

Upvotes: 1

Sayalic
Sayalic

Reputation: 7650

Simple Code(Assume n numbers are stored in array a):

int f()
{
    int cnt=0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            if (a[i]>a[j]) cnt++;
    return cnt%2;
}

If f() returns 0, then it is even permutation and returns 1, then it is odd.

Upvotes: 7

Colonel Panic
Colonel Panic

Reputation: 137574

According to Wikipedia, the sign is determined by the number of inversions (pairs of elements out of order). That gives an O(n**2) algorithm

Upvotes: 1

Colonel Panic
Colonel Panic

Reputation: 137574

Decompose the permutation into a product of independent cycles. Odd cycles are odd. Even cycles are even. Add up.

Upvotes: 0

Harshal Pandya
Harshal Pandya

Reputation: 1624

The sign of the determinant of the permutation matrix for this vector should give you the answer.

Upvotes: 0

Related Questions