I have a list of list.

[
  [4, 5, 6], 
  [5, 6, 7], 
  [8, 9, 10], 
  [20, 21, 22],
  [22,23,24]
]

if the upper_bound(5) of [5,6,7] is less than or equal to lower_bound(6) of [4,5,6] then grp them together and the final list should look like this.

[
  [
    [4, 5, 6], 
    [5, 6, 7]
  ],
  [8, 9, 10],
  [ 
    [20, 21, 22],
    [22,23,24]
  ]

]

How can i do this?

CodePudding user response：

Assuming the number of resulting lists is less than 32, grouping by Range would work.

input
|> Enum.reduce(%{}, fn list, acc ->
  {min, max} = Enum.min_max(list)

  acc |> Map.keys() |> Enum.reduce_while(nil, fn 
    mn..mx, _ when min >= mn and min <= mx and max >= mn and max <= mx -> 
      {:halt, Map.update(acc, mn..mx, & [list | &1])}
    mn..mx, _ when min >= mn and min <= mx -> 
      {:halt, acc |> Map.delete(mn..mx) |> Map.put(mn..max, [list | Map.get(acc, mn..mx)])}
    mn..mx, _ when max >= mn and max <= mx ->
      {:halt, acc |> Map.delete(mn..mx) |> Map.put(min..mx, [list | Map.get(acc, mn..mx)])}
    _, _ -> {:cont, nil}
  end) || Map.put(acc, min..max, [list])
end)
|> Map.values()
|> Enum.map(&Enum.reverse/1)

If the expected number of lists is greater than 32 and the sorting must be preserved, the solution would be way more cumbersome.

CodePudding user response：

This answer assumes that the items are always sequential, as in your example, and that no list completely contains another list.

First, it would be better to work with Ranges, so we first convert the lists to ranges.

Then we can write a recursive algorithm group_ranges/1, which checks each range with its predecessor. If it overlaps (using Range.disjoint?/2), add it to the group. If it doesn't overlap, start a new group.

Finally, since you want non-overlapping ranges to stand alone rather than be in a group of one, we handle that case once the grouping has completed. You could also convert the ranges back to lists at this stage, if that was a strict requirement.

defmodule Example do
  def run do
    [[4, 5, 6], [5, 6, 7], [8, 9, 10], [20, 21, 22], [22, 23, 24]]
    |> Enum.map(fn [head | tail] -> head..List.last(tail) end)
    |> group_ranges()
    |> Enum.map(fn
      [single] -> single
      group -> group
    end)
  end

  def group_ranges([current | rest]), do: do_group_ranges(rest, [current], [])

  defp do_group_ranges([], group, grouped) do
    Enum.reverse([Enum.reverse(group) | grouped])
  end

  defp do_group_ranges([current | rest], [prev | _] = group, grouped) do
    if Range.disjoint?(current, prev) do
      # Create a new group
      do_group_ranges(rest, [current], [Enum.reverse(group) | grouped])
    else
      # Add to existing group
      do_group_ranges(rest, [current | group], grouped)
    end
  end
end

Result:

iex(1)> Example.run
[[4..6, 5..7], 8..10, [20..22, 22..24]]