algorithm - Ocaml作业需要一些建议

Question

We have N sets of integers A1, A2, A3 ... An. Find an algorithm that returns a list containg one element from each of the sets, with the property that the difference between the largest and the smallest element in the list is minimal

示例:

IN: A1 = [0,4,9], A2 = [2,6,11], A3 = [3,8,13], A4 = [7,12]
OUT: [9,6,8,7]

我对这个练习有一个想法，首先我们需要对一个列表中的所有元素进行排序(每个元素都需要分配给它的集合)，所以根据这个输入我们得到这个:

[[0,1],[2,2],[3,3],[4,1],[6,2],[7,4],[8,3],[9,1],[11,2],[12,4],[13,3]]

稍后我们创建所有可能的列表并找到这个具有最小和最大元素之间差异的列表，并像这样返回正确的输出:[9,6,8,7]

我是 ocaml 的新手，所以我对编写这些东西有一些疑问:

1. 我可以创建一个带有 N(无限数量)个参数的函数吗？
2. 我是否应该创建一个新类型，例如对列表来实现假设？

抱歉我的英语不好，希望你能明白我想表达的意思。

Answer 1

这个答案是关于算法部分的，而不是 OCaml 代码。

您可能希望首先实现您提出的解决方案，以获得一个有效的解决方案并将其结果与我现在写的改进解决方案进行比较。

这里是关于如何改进算法部分的提示。考虑对所有集合进行排序，而不仅仅是第一个集合。现在，所有集合中所有最小元素的列表是输出的候选者。要考虑其他候选输出，您如何从那里移动？