Open pygy opened 9 months ago
You don't need to check both sets. Just assert the size. If sizes are equal and all keys of a
are contained in b
, you have equal sets.
if (a.size !== b.size) return false
for (const key of a) {
if (!b.has(key)) return false
}
return true
The proof is relatively straightforward:
a
can't contain duplicates by definition of a set.b
can't contain duplicates by definition of a set.a
and b
are equal iff they are subsets of each other.a
subsets b
, it must have a minimum size of b.size
.b
has an element not in a
.
a
also subsets b
, b.size
must be greater than a.size
.b
has a.size
elements and a
subsets b
, there cannot exist an element in a
not in b
.b
has a.size
elements and a
subsets b
, b
must subset a
.a
has b.size
elements and subsets b
, b
must subset a
. QED.Edit: the same goes for maps. Proof is similar.
if (a.size !== b.size) return false
for (const [key, value] of a) {
if (!b.has(key)) return false
if (!deepEqual(value, b.get(key)) return false
}
return true
For sets, this does an object identity check for membership, I suppose we could do N^2
deepEqual()
checks on the set members to determine if they match... Likewise for maps...