How to decide the sign of the permutation between two ordered set?

Question

Suppose A and B are two arrays of the same size and each without repetitive members. Is there any efficient algorithm that

1.decides whether A and B have the same members

2.if the answer to 1 is true, decides the sign of the permutation which brings A to B(f(A[i])==f(B[i]))?

Thank you.

score 2 · Accepted Answer · edited May 23 '17 at 12:02

You can find the permutation that translates A into B using a hash table:

pos = hash table (value -> position) of B
perm = []
for a in A:
    if a not in pos: return "not the same!"
    perm += [pos[a]]

This part takes O(n) expected time.

Now you just have to find the sign of the permutation. You have at least two options:

Count the number of inversions This is definitely possible in O(n log n) or better
Cycle decomposition This takes only linear time

In fact you can use cycle decomposition directly on your input arrays, that would yield a nice and short implementation.

vsoftco · Answer 2 · 2014-04-21T16:21:01.283

0

An efficient algorithm (O(n^2)) will be the following (assuming there are no duplicates in either arrays).

bool same;
for(int i=0; i<L; i++)
{
    same = false;
    for(int j=0; j<L; j++) // see if A[i] is in B
       if(A[i]==B[j]) 
       {
           same = true; // found A[i] in B
           break;
       }
    if(!same) // A[i] was not found in B 
       break;
}

Here L is the length of the array. At the end of the loops, same will be true if the arrays contain the same elements, false otherwise. Hope this helps.

PS: If the arrays contain duplicates, then this code tells you whether A is included in B or not. But then you can interchange the roles of A and B and decide if B is included in A. If both A included in B AND B included in A, then A=B.

edited Apr 21 '14 at 16:21

answered Apr 21 '14 at 16:14

vsoftco

55,410
12
139
252

Why do you claim O(n^2) is efficient, when the problem can easily be solved by sort&iterate with O(nlogn), or using a hashing solutions with O(n) (average time ans space). There is also the issue of the 'permutation number' which is not mentioned in the answer at all. – amit Apr 21 '14 at 16:25
Well I know one can sort the arrays with a `quicksort`, however this is just a super simple solution that scales as `poly(n)` in 10 lines. But yes, you're right, one can do better, I didn't claim this to be the lower bound :) – vsoftco Apr 21 '14 at 16:28
I would argue that the faster solutions are even simpler. – Niklas B. Apr 21 '14 at 19:13

barak manos · Answer 3 · 2014-04-21T16:57:15.857

Is this a general algorithmic question, or are you asking for a specific (language-based) implementation?

For question #1, simply sort each array in O(nlog(n)) and then compare the arrays in O(n).

If the range of input values is not significantly large, then you can use a direct hash table instead and perform the sorting phase in O(n), thus reducing the overall complexity from O(nlog(n)) to O(n).

In Java, you can achieve this using a HashMap instance. I'm not sure about the internal implementation of this class, but it might achieve the same performance even for a large range of input values.

For question #2, since there are no repetitive elements, the total number of permutations is n!.

You can calculate the permutation-ID of each array within the entire group of permutations, and then use the pair of IDs that you have calculated in order to uniquely identify the mapping between the two arrays.

For example, suppose that A = {3,2,1,4} and B = {4,1,3,2}.

The total number of permutations is 24, so each permutation can be mapped to an ID between 0 and 23:

1,2,3,4 ==>  0
1,2,4,3 ==>  1
1,3,2,4 ==>  2
1,3,4,2 ==>  3
1,4,2,3 ==>  4
1,4,3,2 ==>  5
2,1,3,4 ==>  6
2,1,4,3 ==>  7
2,3,1,4 ==>  8
2,3,4,1 ==>  9
2,4,1,3 ==> 10
2,4,3,1 ==> 11
3,1,2,4 ==> 12
3,1,4,2 ==> 13
3,2,1,4 ==> 14
3,2,4,1 ==> 15
3,4,1,2 ==> 16
3,4,2,1 ==> 17
4,1,2,3 ==> 18
4,1,3,2 ==> 19
4,2,1,3 ==> 20
4,2,3,1 ==> 21
4,3,1,2 ==> 22
4,3,2,1 ==> 23

Array A is mapped to ID 14
Array B is mapped to ID 19
The mapping f(A,B) = (14,19)

If you want this function to yield a single value, then you can use n!*id1+id2 instead of id1,id2.

Alternatively, you can define the mapping function f(A,B) to return an array of index-changes.

For example, suppose that A = {3,2,1,4} and B = {4,1,3,2}.

The element at index 0 moves to index 2, so the index-change is +2
The element at index 1 moves to index 3, so the index-change is +2
The element at index 2 moves to index 1, so the index-change is -1
The element at index 3 moves to index 0, so the index-change is -3

Hence, f({3,2,1,4},{4,1,3,2}) should return the array {2,2,-1,-3}.

How to decide the sign of the permutation between two ordered set?

3 Answers3