I have two Numpy arrays A and B, I want to find whether sorted(A) == sorted(B) or not? For ex: If A = [5,3,2,4] and B = [3,2,5,4], then it should evaluate to True.
Can this be achieved in linear time?
Asked
Active
Viewed 63 times
0
-
set(A) == set(B) – Lamanus Aug 02 '19 at 14:27
-
2set doesn't work if the lists have repeat values that must match up. – Aug 02 '19 at 14:28
-
1Ya right @MikeSperry suppose if `A = [1,1,2,3]` and `B = [3,1,2]`, then `set(A)==set(B)` would return TRUE but the answer is actually False. @Lamanus – Aug 02 '19 at 14:31
-
What's wrong with `sorted(A) == sorted(B)` in your case? Can you tell us more about your constraints? – Aug 02 '19 at 14:31
-
what about numpy.unique(a) == numpy.unique(b) – Lamanus Aug 02 '19 at 14:32
-
@MikeSperry The size of the list could be as large as 10^8, so I was looking for a more optimized method like something in O(n). – Aug 02 '19 at 14:33
-
@SomShekharMukherjee Take a look at my O(n) solution below – alexanderhurst Aug 02 '19 at 14:58
3 Answers
5
How about Counter from collections
>>> import collections
>>> a = collections.Counter([1,1,2,3])
>>> b = collections.Counter([3,1,2])
>>> a == b
False
>>> a = collections.Counter([1,1,2,3])
>>> b = collections.Counter([3,1,2,1])
>>> a == b
True
Construction happens in O(n) time for each list
edit: If anyone is unfamiliar with what counter does. It goes through the list and creates what is essentially a dictionary mapping of value to the number of occurrences that value.
So once we create these dictionaries of the form a = {'1': 2, '2': 1...} Which takes up to O(n) time we can compare the two dictionaries which also takes O(n) time.
alexanderhurst
- 456
- 3
- 8
1
In this case adding brackets works quite fast:
A = [5,3,2,4]
B = [3,2,5,4]
print((sorted(A) == sorted(B)))
Which yields:
True
Fokke
- 81
- 7
-
if there is a dupe for ex, A = [1,1,2,3] and B = [1,2,3] it will not be same. – Lamanus Aug 02 '19 at 14:34
0
Try this. If a and b are
a = np.array([1,2,3,3,2,3,4])
b = np.array([1,2,3,4])
then,
np.array_equal(np.unique(a), np.unique(b))
True
Lamanus
- 12,898
- 4
- 21
- 47