如何对符合特定条件的列表进行分组

Question

我有一个列表。

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

如果 [5,6,7] 的 upper_bound(5) 小于或等于 [4,5,6] 的 lower_bound(6) 则将它们放在一起并最终列表应如下所示。

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

]

我该怎么做？

Answer 1

假设结果列表的数量少于 32，按 Range 分组将有效。

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)

如果列表的预期数量大于32，并且必须保留排序，则解决方案会更麻烦。

Answer 2

此答案假设项目始终是连续的，如您的示例所示，并且没有列表完全包含另一个列表。

首先，最好使用 Ranges，因此我们首先将列表转换为范围。

然后我们可以编写一个递归算法group_ranges/1，它检查每个范围与其前导。如果重叠（使用 Range.disjoint?/2），将其添加到组中。如果不重叠，开始一个新的组。

最后，由于您希望 non-overlapping 个范围独立而不是一组，我们会在分组完成后处理这种情况。如果这是一个严格的要求，您也可以在此阶段将范围转换回列表。

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

结果：

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

如何对符合特定条件的列表进行分组

How to group a list of list that matches certain condition

algorithm

elixir