Compare arrays as (multi-) sets

Question

I'm looking for an efficient way to find out whether two arrays contain same amounts of equal elements (in the == sense), in any order:

foo = {/*some object*/}
bar = {/*some other object*/}

a = [1,2,foo,2,bar,2]
b = [bar,2,2,2,foo,1]

sameElements(a, b) --> true

PS. Note that pretty much every solution in the thread uses === and not == for comparison. This is fine for my needs though.

Answer 1

You can implement the following algorithm:

• If a and b do not have the same length:
  • Return false.
• Otherwise:
  • Clone b,
  • For each item in a:
    • If the item exists in our clone of b:
      • Remove the item from our clone of b,
    • Otherwise:
      • Return false.
  • Return true.

With Javascript 1.6, you can use every() and indexOf() to write:

function sameElements(a, b)
{
    if (a.length != b.length) {
        return false;
    }
    var ourB = b.concat();
    return a.every(function(item) {
        var index = ourB.indexOf(item);
        if (index < 0) {
            return false;
        } else {
            ourB.splice(index, 1);
            return true;
        }
    });
}

Note this implementation does not completely fulfill your requirements because indexOf() uses strict equality (===) internally. If you really want non-strict equality (==), you will have to write an inner loop instead.

Answer 2

Like this perhaps?

var foo = {}; var bar=[];
var a = [3,2,1,foo]; var b = [foo,1,2,3];

function comp(a,b)
{
    // immediately discard if they are of different sizes
    if (a.length != b.length) return false;

    b = b.slice(0); // clone to keep original values after the function

    a.forEach(function(e) {
        var i;
        if ((i = b.indexOf(e)) != -1)
            b.splice(i, 1);
    });

    return !b.length;
}

comp(a,b);