How to reliably make a Python set?

So I am trying to make a set kind of like Python’s set, for those who don’t know what that is, a Python set is essentially an unordered array, which are useful for comparing multiple things without worrying about order. And they cannot contain duplicates. Additional duplicates are discarded.

Here is sample code:

set1 = { "Hey", "There", "How ya been?" }
set2 = { "How ya been?", "There", "Hey" }
print(set1 == set2) # True

I believe I can handle the rest, the only thing I am unsure of doing is testing for equality. I will be using __eq to overload the == operator to return true if the sets have the same content regardless of order. But how should I do this.

Ok so as if an angel whispered a solution into my ear I found a way to do it.

Here is code for if any future readers read it:

__eq = function(lhs, rhs)
	for _, value in ipairs(lhs) do
		if not table.find(rhs, value) then
			return false
		end
	end
	return true
end

It just checks every value, if there is no value in one of the sets, it’s not a match.

2 Likes

This will incorrectly return true for {1} == {1, 2, 3} and other cases where lhs is a proper subset of rhs. It is necessary to check both directions. It would also be more accurate to store the values in dictionary keys mapped to true so that lookup is a constant time operation. That also solves the duplicates issue.

here’s a more hackish way to check whether two tables contain the same keys

local function equal(a, b)
	local diff = {}
	for k in next, a do
		diff[k] = true
	end
	for k in next, b do
		diff[k] = (not diff[k]) and true or nil
	end
	return next(diff) == nil
end

although that is unnecessary, this is fine

local function equal(a, b)
	for k in next, a do
		if not b[k] then return false end
	end
	for k in next, b do
		if not a[k] then return false end
	end
	return true
end
2 Likes