Check for equality in the contents of two arrays ignoring order

2 views (last 30 days)
Bill Tubbs
Bill Tubbs on 17 Oct 2021
Commented: Bill Tubbs on 18 Oct 2021
I want to check that the contents of two arrays are equal, ignoring ordering of the elements.
I couldn't find an existing answer on this for some reason. There are two parts to this question, depending on whether the arrays are sets or not.
1. Checking equality for two sets
Assuming there are no duplicates I could use set operaions but it doesn't look like Matlab has sets, only set operations, and I couldn't find a setisequal function. Also, there are so many possible ways to do it I'm not sure which is the best:
A = [1 3]; B = [3 1];
assert(isequal(intersect(A, B), union(A, B)))
or
assert(isempty(setdiff(A,B)) & isempty(setdiff(B,A)))
or
assert(all(ismember(B, A)) & all(ismember(A, B)))
or
assert(isequal(unique(A), unique(B)))
However, if there may be different numbers of duplicates in either of the two arrays, then the above set operations will ignore them.
2. Checking equality for non-sets
This is the best I could think of in this case but it involves two sort operations which is quite inefficient:
assert(isequal(sort(A), sort(B)))
No doubt there is something very simple that I am missing here...

Accepted Answer

Walter Roberson
Walter Roberson on 17 Oct 2021
%sets case
A = [1 3]; B = [3 1];
isequal(unique(A), unique(B))
ans = logical
1
For the sets case, a different approach just might be faster:
numel(A) == numel(B) && all(ismember(A, B))
ans = logical
1
%nonset case:
A = [1 3]; B = [3 1 3];
isequal(unique(A), unique(B))
ans = logical
1
  7 Comments
Bill Tubbs
Bill Tubbs on 18 Oct 2021
You have a good point about tolerances. The only solution that works at the moment is therefore something like this:
assert(all(abs(sort(A) - sort(B)) < 1e-6))
I'm happy with this t.b.h.

Sign in to comment.

More Answers (2)

Bill Tubbs
Bill Tubbs on 17 Oct 2021
I think this might be the answer for case 1 (A & B are sets):
A = [1 3]; B = [3 1];
assert(isempty(setxor(A, B)))
A = [1 3]; B = [3 1 2];
assert(~isempty(setxor(A, B)))
Note: Doesn't work in the case that A or B are not sets:
A = [1 3]; B = [3 1 3];
assert(~isempty(setxor(A, B)))
Assertion failed.

Jan
Jan on 17 Oct 2021
unique, setdiff, union and ismember call the function sort also internally. So
% assert(isequal(sort(A), sort(B)))
Is a very efficient solution.
A = randperm(1e6, 1e6);
B = randperm(1e6, 1e6);
tic
for k = 1:10
isequal(sort(A), sort(B));
end
toc
Elapsed time is 1.138481 seconds.
tic
for k = 1:10
all(ismembc(A, sort(B))); % Internal helper of ISMEMBER
end
toc
Elapsed time is 1.453001 seconds.
If repeated elements are existing:
A = randi([0,1e3], 1, 1e6);
B = randi([0,1e3], 1, 1e6);
tic
for k = 1:10
isequal(unique(A), unique(B));
end
toc
Elapsed time is 0.676562 seconds.
tic
for k = 1:10
numel(A) == numel(B) && all(ismember(A, B));
end
toc
Elapsed time is 0.980030 seconds.
tic
for k = 1:10
As = sort(A);
Au = As([true, diff(As) ~= 0]); % Remove repeated elements
Bs = sort(B);
Bu = Bs([true, diff(Bs) ~= 0]); % Remove repeated elements
isequal(Au, Bu);
end
toc
Elapsed time is 0.781304 seconds.
In R2018b the last method is faster than isequal(unique(A), unique(B)). Try this locally.
  1 Comment
Bill Tubbs
Bill Tubbs on 18 Oct 2021
Thanks for the timings. Only assert(isequal(sort(A), sort(B))) produces the desired result in the case of unordered lists (not sets) so I guess there is no other option.
Also, note that these solutions you proposed do not produce the correct result:
assert(~all(ismembc([1 2], sort([1 2 3]))))
Assertion failed.
A = [1 2 2]; B = [1 2 3];
assert(~(numel(A) == numel(B) && all(ismember(A, B))))
Assertion failed.

Sign in to comment.

Products


Release

R2020a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!