Check for equality in the contents of two arrays ignoring order

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...

Answer 1

[Walter Roberson]

%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

[Bill Tubbs]

Thanks, the first answer makes sense. But in the second case (non-sets: A = [1 3]; B = [3 1 3];) I want the answer to be false not true.

[Bill Tubbs]

For context: I am comparing algorithms that calculate lists of eigenvalues. There may be multiple identical values but the number of each must be the same in each list.

[Walter Roberson]

But is the ismember() version faster than the isequal() of unique?

And in the sets case, is unique() faster than sort()?

N = 100000;
T = 25;
A = randperm(N);
B = randperm(N);
C = randperm(N); C(randi(N,1,5)) = randi(N,1,5);  %likely to produce duplicates

[eteu, etes, etnel, nteu, ntes, ntnel] = deal(zeros(1,T));

for K = 1 : T; 
    %case where they are in fact equal
    eteu(K) = timeit(@() isequal(unique(A), unique(B)),0);
    etes(K) = timeit(@() isequal(sort(A), sort(B)), 0);
    etnel(K) = timeit(@() numel(A) == numel(B) && all(ismember(A,B)));

    %case where they are not equal
    nteu(K) = timeit(@() isequal(unique(A), unique(C)),0);
    ntes(K) = timeit(@() isequal(sort(A), sort(C)), 0);
    ntnel(K) = timeit(@() numel(A) == numel(C) && all(ismember(A,C)));
end

X = categorical({'eteu', 'etes', 'etnel', 'nteu', 'ntes', 'ntnel'});
Y = [mean(eteu), mean(etes), mean(etnel), mean(nteu), mean(ntes), mean(ntnel)];
bar(X, Y)

Analysis:

checking isequal() of sort() is slightly faster than checking isequal() of unique(), but checking isequal() of unique() is statistically the same as all(ismember) when the sets are the same size (if they are potentially different sizes then checking the size first could be a big advantage.)

The difference between checking isequal() of sort() compared to isequal() of unique() is small enough that it is probably not worth using two different code paths: might as well use the isequal() of unique() for both cases.

[Walter Roberson]

In the eigenvalue problem, how do you plan to deal with the fact that identical eigenvalues might or might not come out identical depending on the scale of the matrices and the magnitude of the other eigenvalues? Indeed, that they will not often come out as identical to within default roundoff tolerances.

Multiset case:

numel(A) == numel(B) && isequal(sort(A), sort(B))

[Bill Tubbs]

It's maybe a good point that the eigenvalues produced by eig() might not be identical to the eigenvalues specified (although they have so far) but I'm also comparing two implementations of the same algorithm, so they should be identical to each other.

[Walter Roberson]

%implementation #1
0.1 + 0.2 - 0.3

ans = 5.5511e-17

%implementation #2
0.1 - 0.3 + 0.2

ans = 2.7756e-17

Two implementation of the same algorithm involving floating point values will typically not return identical results.

[Bill Tubbs]

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.

Answer 2

[Bill Tubbs]

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.

Answer 3

[Jan]

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.

[Bill Tubbs]

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.