5

Possible Duplicate:
Check if array B is a permutation of A

Given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space?

The first solution that came to my mind is that is using XOR, i.e. XOR all the elements of a and b and if the resultant is 0 which means that b is a permutation of a. But he gives examples where this approach fails. For e.g - 

a: [1 6 0 0 4] -- b: [1 0 6 1 5]
a: [1 6 0 0 5] -- b: [1 0 6 1 4]

Any one having any idea, that how to do it in O(n) time and O(1) space?

Community
  • 1
  • 1
Ravi Gupta
  • 6,258
  • 17
  • 56
  • 79
  • 6
    are the integers in a bounded range? One can imply in-place radix sort if they are – amit Jun 07 '12 at 09:35
  • @amit: no... but I am interested in knowing about that too... kindly add that case as an answer... – Ravi Gupta Jun 07 '12 at 11:57
  • @RaviGupta : well, i dont know O(n) solution but one solution which is efficient is first check length of the arrays and if it is same then sort both the arrays using any O(nlogn) algorithm. Then compare the elements if they are equal then they are permutation of each other. And space complexity would be O(1). – ATR Jun 08 '12 at 06:31

3 Answers3

2

In the case of a bounded range of integers - let that range be [n,m] such that m-n = U you can sort the arrays using in place radix sort, also discussed in this great post.

After you have two sorted arrays - a simple iteration on both can give you the answer - the original arrays are permutations of each other if and only if the sorted arrays are identical.

Note:
There is some "cheating" in this answer [thus I did not post it until the OP asked for it in comments..], since the time complexity of it is O(nlogU), and space is O(logU). However, for bounded ranges - we can assume O(logU) = O(1), and for these cases we get O(n) time and O(1) space.

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
1

If your set elements are non-negative, and you have an unbounded integer type (a BigInteger or similar) available, you could define a function over a set A:

C(A) = product(p_(a+1))) for each a in A

where p_nis the nth prime number. Then C depends only on the values in A, rather than their order; and any change to the values changes C.

For example, 

C([1 6 0 0 4]) = p_2.p_7.p_1.p_1.p_5 = 3.17.2.2.11 = 2244

(and obviously any set with the same elements has the same C, whatever the order), and

C([1 6 0 1 4]) = p_2.p_7.p_1.p_2.p_5 = 3.17.2.3.11 = 3366

so we know these sets are different. This uses the fundamental theorem of arithmetic which states that any integer greater than 1 can be written as a unique product (up to ordering of the factors) of prime numbers. Or maybe it uses a corollary. I just made this method up, so it might not work. This post is not an attempt at a proof of its correctness...

AakashM
  • 62,551
  • 17
  • 151
  • 186
  • 1
    The solution uses non constant (and even not linear) space. The product is expansive to both calculate and store. Note that for calculating n! (which is likely to be smaller then the product you need) it needs `O(log(n!)) = O(nlogn)` bits, thus this solution is `O(nlogn)` space and time. – amit Jun 07 '12 at 09:46
  • @AakashM i didnt get how you tried to co-relate product of primes to given question – Imposter Jun 07 '12 at 09:50
  • Imposter: http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic – sdcvvc Jun 07 '12 at 15:52
  • @amit is there a 'terms of reference' (sorry, don't know the technical term) issue here? By which I mean: sometimes in the literature, any single operation on an integer `n` is called `O(1)`, whereas at other times it's `O(number of bits in binary representation of n)`. Do you know what I mean and if so can you tell me what terms should be googling for more? – AakashM Jun 07 '12 at 16:38
  • 1
    @AakashM: When refering to integers ops and space as `O(1)` - we do it because we assume numbers are smaller then a constant size, usually 32 bits. However, when using product iteratively, this assumption cannot be taken. Note that `13! > 2^32`. Because of it, we are going to need an external library (such as java's `BigInteger`) to represent huge numbers. However, this library uses non constant space amount. The space consumption of BigIntegers libraries is at best `O(logN)` where `N` is the number represented. Because of it, to represent `n!` we will nee `O(log(n!)) = O(nlogn)` space. – amit Jun 07 '12 at 17:04
  • @AakashM: This model in realistic version requires that the numbers are bounded by at most polynomial of the input. There is a known factoring algorithm that runs in polynomial time (!) if you dispose of this assumption. Reference: [A Computational Introduction to Number Theory and Algebra](http://www.shoup.net/ntb/ntb-v2.pdf), paragraphs 3.3 and 3.6. – sdcvvc Jun 08 '12 at 06:04
1

Your exclusive-OR solution is basically a hash-based solution, but using a poor quality hash function.

What you want is a hash function that...

  1. Gives hashes that are extremely unlikely to collide, so they can be treated as unique identifiers for the integers. Git uses SHA-1 hashes to identify source code versions, with a probability of collision so low it can be ignored.

  2. Commutative (like xor and plus) and probably associative, so the order of the items doesn't change the resulting hash.

That second requirement is probably the awkward one. I've spent a little time in Google, but just got scared of words like "Quasigroup".