GOAL: Given a list of sets find/create the the union of intersecting sets. This can be seen as finding all the components in a network graph.
https://en.wikipedia.org/wiki/Component_(graph_theory)
I came up with a solution, though it took like 5hrs! Ack! So I posted my solution for comment to the elixirforum here:
https://elixirforum.com/t/list-of-sets-find-intersecting-sets/33368
And the solution is/was (I called it meld):
defp meld([], [], [], result) do
result
end
defp meld([item|rest], [], [], result) do
meld(rest, [item], result, [])
end
defp meld(rest, [item], [], result) do
meld(rest, [], [], [item|result])
end
defp meld(rest, [item], [head|tail], result) do
if MapSet.disjoint?(item, head) do
meld(rest, [item], tail, [head|result])
else
meld(rest, [MapSet.union(item, head)], tail, result)
end
end
def do_meld([item|rest]) do
meld(rest, [], [], [item])
end
Explanation starting at do_meld which is the external API: Given a list of sets, begin by reducing on the given set, with the 1st set as the resultant list of the union of intersecting sets.
def do_meld([item|rest]) do
meld(rest, [], [], [item])
end
Now, I have found when writing recursive functions I start at the end, kinda like when you write fib or fac you identify the "base" return values. So, here once we dont have any more sets to meld we just return the result, thus you can see that the 1st and 4th arguments are essentially the input and output of meld.
defp meld([], [], [], result) do
result
end
The basis of the recursion occurs when there is at least 1 more set to meld into the result. It then calls a 2nd meld with an item to be melded into the result.
def meld([item|rest], [], [], result) do
meld(rest, [item], result, [])
end
The 3rd recursion is the case where the result into which the item is to be melded is an empty list in which case the item is simply to make it
def meld(rest, [item], [], result) do
meld(rest, [], [], [item|result])
end
Describe this
def meld(rest, [item], [head|tail], result) do
if MapSet.disjoint?(item, head) do
meld(rest, [item], tail, [head|result])
else
meld(rest, [MapSet.union(item, head)], tail, result)
end
end
Describe this
.
.
.
.
.