0

我们有 N 组整数 A1, A2, A3 ... An。找到一种算法，该算法返回一个列表，该列表包含每个集合中的一个元素，其属性是列表中最大元素和最小元素之间的差异最小

例子：

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. 我应该创建一个新类型，比如对列表来实现假设吗？

对不起我的英语不好，希望你能理解我想表达的意思。

4

4 回答 4

1

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

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

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

于 2012-11-12T09:51:57.113 回答
0

您的方法听起来不是很有效，有n许多集合，每个集合都有元素，x_i您的排序列表将包含(n * x_i)元素，您可以从中生成的子列表的数量为：（(n * x_i)!阶乘）

我想提出一种不同的方法，但你必须弄清楚细节：

  1. 使用设置的标识符标记（索引）每个元素（就像您所做的那样）。

  2. 分别对每组进行排序。

  3. 构建与您想要的结果完全相反的结果！

  4. 优化！

我希望你能自己弄清楚第 3、4 步... :)

于 2012-11-12T10:14:08.810 回答
0

我只是要回答你的问题，而不是评论你提出的解决方案。（但我认为你必须在完成之前再做一些工作。）

  1. 您可以编写一个接受列表列表的函数。这与允许任意数量的参数几乎相同。但实际上它只有一个参数（就像 OCaml 中的所有函数一样）。

  2. 您可以只使用列表和元组等内置类型，而无需显式创建或声明它们。

这是一个示例函数，它采用列表列表并将它们组合成一个大长列表：

let rec concat lists =
  match lists with
  | [] -> []
  | head :: tail -> head @ concat tail
于 2012-11-12T07:16:09.057 回答
0

这是您在问题中描述的帮助您入门的例程。请注意，我没有注意效率。为了清楚起见，还添加了反向应用（管道）运算符。

let test_set = [[0;4;9];[2;6;11];[3;8;13]; [7;12]] 

let (|>) g f = f g

let linearize sets = 
  let open List in sets 
    |> mapi (fun i e -> e |> map (fun x -> (x, i+1) )) 
    |> flatten |> sort (fun (e1,_) (e2, _) -> compare e1 e2)

let sorted = linearize test_set
于 2012-11-12T07:20:11.237 回答