根据不同年龄组的值(value)观将其组合在一起的算法

Question

假设我们有一组年龄组和一组每个年龄组的人数

例如:

Ages = ("1-13", "14-20", "21-30", "31-40", "41-50", "51+")
People = (1, 10, 21, 3, 2, 1)

如果每个组中的人数少于 5 人，我希望有一个算法将这些年龄组与以下逻辑结合起来。到目前为止，我的算法执行以下操作:

1. 从最后一个元素(例如“51+”)开始，你能将它与下一组组合起来吗？ (此处为“41-50”)如果是，请添加数字 1+2 并组合它们的标签。所以我们得到以下内容

   Ages = ("1-13", "14-20", "21-30", "31-40", "41+")
   People = (1, 10, 21, 3, 3)
   

2. 再拿最后一个(这里是“41+”)。你能把它和下一组(31-40)结合起来吗？答案是肯定的，所以我们得到:

   Ages = ("1-13", "14-20", "21-30", "31+")
   People = (1, 10, 21, 6)
   

3. 由于 31+ 组现在有 6 名成员，我们无法将其折叠到下一个组中。

4. 我们也不能将“21-30”折叠成下一个“14-20”

5. “14-20”也有 10 人 (>5)，所以我们也不对此做任何事情

6. 对于第一个 ("1-13")，因为我们只有一个人，而且它是最后一组，我们将它与下一组 "1​​4-20"结合起来，得到以下内容

   Ages = ("1-20", "21-30", "31+")
   People = (11, 21, 6)
   

我有一个这个算法的实现，它使用许多标志来跟踪是否有任何数据被更改，并且它在两个数组上进行多次传递以完成此任务。

我的问题是，您是否知道做同样事情的有效方法？任何可以提供帮助的数据结构？任何可以帮助我做同样事情而无需做太多簿记的算法都会很棒。

更新:一个激进的例子是 (5,1,5)

在第一遍中它变成了 (5,6) [将右边的折叠成中间的]

那么我们有 (5,6)。我们不能触及 6，因为它大于我们的阈值:5。所以我们转到下一个(最左边的元素 5)，因为它小于或等于 5，并且因为它是左边的最后一个，所以我们将它与右边的元素组合在一起。所以我们最终得到 (11)

Answer 1

这是一个从左到右合并算法的 OCaml 解决方案:

let close_group acc cur_count cur_names =
  (List.rev cur_names, cur_count) :: acc

let merge_small_groups mini l =
  let acc, cur_count, cur_names =
    List.fold_left (
      fun (acc, cur_count, cur_names) (name, count) ->
        if cur_count <= mini || count <= mini then
          (acc, cur_count + count, name :: cur_names)
        else
          (close_group acc cur_count cur_names, count, [name])
    ) ([], 0, []) l
  in
  List.rev (close_group acc cur_count cur_names)

let input = [
  "1-13", 1;
  "14-20", 10;
  "21-30", 21;
  "31-40", 3;
  "41-50", 2;
  "51+", 1
]

let output = merge_small_groups 5 input
(* output = [(["1-13"; "14-20"], 11); (["21-30"; "31-40"; "41-50"; "51+"], 27)] *)

如你所见，从左向右合并的结果可能不是你想要的。

根据目标，合并总和最小的一对连续元素并迭代直到所有计数都高于最小值 5 可能更有意义。