czrpb

czrpb

List of Sets: Find Intersecting Sets

This took me way too long and I think its right/working, but … am I missing a better solution?

defmodule IntersectingSets do
  def meld([], [], [], result) do
    result
  end

  def meld([item|rest], [], [], result) do
    meld(rest, [item], result, [])
  end

  def meld(rest, [item], [], result) do
    meld(rest, [], [], [item|result])
  end

  def meld(rest, [item], [head|tail], result) do
    cond do
      MapSet.intersection(item, head) |> MapSet.size == 0 ->
        meld(rest, [item], tail, [head|result])
      true ->
        meld(rest, [MapSet.union(item, head)], tail, result)
    end
  end

  def meld([item|rest]) do
    meld(rest, [], [], [item])
  end
end

Marked As Solved

mudasobwa

mudasobwa

Creator of Cure

Actually, it might be even simplified. As @saverio-kantox pointed out to me, case is not needed at all. The second clause perfectly does in both cases:

Enum.reduce(sets, [], fn set, sets ->
  {disjoined, joined} =
    Enum.split_with(sets, &MapSet.disjoint?(&1, set))
  [Enum.reduce(joined, set, &MapSet.union/2) | disjoined]
end)

For empty joined, reduce/3 would immediately return the initial accumulator.

Also Liked

al2o3cr

al2o3cr

FWIW, you’ll get much better responses if you describe what this code is supposed to do.

Tracing through an example by hand, it will return the whole input list if every given MapSet intersects with every other one. Non-intersecting sets will be combined.

Some general notes on structure:

  • the second argument is always patterned-matched against either [] or [item]. Consider removing the useless list wrapping and use nil vs item instead

  • +1 to using if over a cond with one non-default branch

  • consider using MapSet.disjoint?/2 - there’s probably a tiny performance benefit to not constructing the whole result of MapSet.intersection, but more importantly it’s clearer what the intent of the check is

kokolegorille

kokolegorille

Why so complicate?

iex> m1 = MapSet.new([1, 2, 3])
#MapSet<[1, 2, 3]>
iex> m2 = MapSet.new([2, 3, 4])
#MapSet<[2, 3, 4]>
iex> MapSet.intersection m1, m2
#MapSet<[2, 3]>

… or maybe I didn’t get what You want

UPDATE: Well, I didn’t get what You want to do… better use data and expected result in that case.
Also, I would not write it like this… first the main entry function, then the rest private…

defmodule Koko do
  def meld(list) do
    ....
  end

  defp do_meld(a, b, c, d) do
    ....
  end
end

With your code, You need to start to read from the bottom.

mudasobwa

mudasobwa

Creator of Cure

You might use Enum.reduce/3 in the following way (untested, but it should work):

Enum.reduce(sets, [], fn set, sets ->
  case Enum.split_with(sets, &MapSet.disjoint?(&1, set)) do
    {_, []} ->  # not a single join, totally alien, appending
      [set | sets]
    {disjoined, joined} ->  # ⇓⇓⇓ here is a trick ⇓⇓⇓
      [Enum.reduce(joined, set, &MapSet.union/2) | disjoined]
  end
end)

The only interesting thing here is that once we discovered all the sets joined the tested one, all of them are to be joined.

czrpb

czrpb

(cant figure out how to add some description to the original post?!! i must be a dummy! :slight_smile:)

addressing replies:

Goal: Given a list of sets, return a list of the union of intersecting sets. Can think of this as a finding all the components in a network graph. https://en.wikipedia.org/wiki/Component_(graph_theory)

Algo: Reduce the set, and on each reduction, reduce the found intersecting sets and merge (union) the current set (from the 1st/outside reduce) into the appropriate intersecting set.

  def meld2(list_of_sets) do
    list_of_sets
    |> Enum.reduce([],
      fn
        next_set, [] ->     # seems necessary for a list of size 1?
          [next_set]
        next_set, disjointed_sets ->
          disjointed_sets
          |> Enum.reduce({next_set, []},
             fn disjointed_set, {melded_set, new_disjointed_set} ->
               if MapSet.disjoint?(melded_set, disjointed_set) do
                 {melded_set, [disjointed_set|new_disjointed_set]}
               else
                 {MapSet.union(melded_set, disjointed_set), new_disjointed_set}
               end
            end
          )
          |> (fn {melded, others} -> [melded|others] end).()    # people dont like anon funcs, something better?
      end
    )
  end

Where Next?

Popular in Questions Top

Brian
What is the proper way to load a module from a file in to IEX? In the python world, doing something like this pretty standard: from ....
New
gshaw
What is the idiomatic way of matching for not nil in Elixir? E.g., First way: defp halt_if_not_signed_in(conn, signed_in_account) when...
New
sergio_101
I am VERY much an elixir newbie. I have taken one elixir course and one phoenix course on Udemy. During that course, I saw the instructor...
New
SoCreat
i’m a new one to elixir which editor can i use vs code? or atom? Thanks! :smiley:
New
sacepums
Hey guys. I'm new to elixir and im really stocked about it. But I ran into a bit of problem - I need to convert a date sting, for examp...
New
hariharasudhan94
I would like to know what is the best IDE for elixir development?
New
mgjohns61585
Could someone help me? I'm making my first elixir program, number guessing game. I can't figure out how to convert the user's guess from ...
New
mathew4509
I have a list say x = ["23gh", "56kh", "97mh"] I would like to pass each element to Val in each iteration. Say, in iteration 1 -------...
New
LegitStack
I’m trying to make a websocket server in Phoenix or raw Elixir. I heard about gun, I think I could use cowboy, but since I’m not that sma...
New
Mooodi
Given a string, how can I get access to its character by index? Enum.at("my_string", 2) doesn't work. Or rather, not char, but a substr...
New

Other popular topics Top

sorentwo
Hello! tl;dr Announcing Oban, an Ecto based job processing library with a focus on reliability and historical observability. After spen...
977 41022 311
New
sergio
In Ruby, I can go: User.find_by(email: "foobar@email.com").update(email: "hello@email.com") How can I do something similar in Elixir? ...
New
sergio
I couldn’t find any guides that worked well with Phoenix 1.6.0 and esbuild. I hope this helps people test the waters and eases you into t...
New
lastday4you
I wanted to check elixir version in phoenix because i found that my elixir is 1.5 but when i use Enum.chunk_by it said the function is un...
New
minhajuddin
I have seen a lot of code which picks the first element from a list using Enum.at(0) instead of List.first. Is there a reason why people ...
New
chensan
I have a User schema with a :from_id field set to type :string: defmodule TweetBot.Repo.Migrations.CreateUsers do use Ecto.Migration ...
New
shahryarjb
Hello, I have map which I want to convert it to string like this: the map: %{last_name: "tavakkoli", name: "shahryar"} the string I ne...
New
Qqwy
Original source of discussion: This topic on the Pragmatic Programmers' Functional Web Development with Elixir, OTP, and Phoenix forum. ...
New
skosch
To my knowledge, put_in, Map.update etc. all have the one limitation of not automatically creating intermediate keys when needed (for exa...
New
siddhant3030
Hi, I have to write a raw query for one of my project. But till now I have used ecto queries and don’t have much experience writing raw ...
New

We're in Beta

About us Mission Statement